Author Topic: TT's Maths Thread (Read 118808 times) Tweet Share

humph · « **Reply #165 on:** November 25, 2009, 01:40:22 pm »

Quote from: Ahmad on November 25, 2009, 01:19:10 pm

It's asymptotically $\sum_{i=1}^{\lfloor x\rfloor} \int_{i}^{i+1} \log \left(\frac{t}{i}\right) dt = \sum_{i=1}^{\lfloor x\rfloor} \left( (i+1) \log(1+\frac{1}{i}) - 1\right) \le \sum_{i=1}^{\lfloor x\rfloor} \frac{1}{i} = O(\log x)$

where I used $x \ge \log(1+x)$ which is true because $e^x \ge 1+x$ . Is that how you did it?

Nah. I was trying to show that
$\sum_{n \leq x}{\log n} = x\log x - x + O(\log x).$
Here's what I did:
$\sum_{n \leq x}{\log n} = \sum_{n \leq x}{\int^{n+1}_{n}{\log n \: dt}} = \int^{\left\lfloor x\right\rfloor + 1}_{1}{\log \left\lfloor t\right\rfloor \: dt} = \int^{x}_{1}{\log t \: dt} + \int^{2}_{1}{\log \left(\frac{\left\lfloor t\right\rfloor}{t}\right) \: dt} + \int^{x}_{2}{\log \left(\frac{\left\lfloor t\right\rfloor}{t}\right) \: dt} + \int^{\left\lfloor x\right\rfloor + 1}_{x}{\log \left\lfloor t\right\rfloor \: dt}.$
Then $\int^{x}_{1}{\log t \: dt} = x \log x - x$ , and
$0 \leq \int^{\left\lfloor x\right\rfloor + 1}_{x}{\log \left\lfloor t\right\rfloor \: dt} = (\left\lfloor x\right\rfloor + 1 - x) \log \left\lfloor x\right\rfloor = (1 - \{x\}) \log(x - \{x\}) \leq \log x.$
Also
$0 \geq \int^{x}_{2}{\log \left(\frac{\left\lfloor t\right\rfloor}{t}\right) \: dt} = \int^{x}_{2}{\log\left(1 - \frac{\{t\}}{t}\right) \: dt},$
and then using $\log(1-z) = \sum^{\infty}_{n=1}{z^n/n} \leq \sum^{\infty}_{n=1}{z^n} = z/(1-z)$ for $|z| < 1$ and using the estimate $0 \leq \{t\} < 1$ , we get
$\int^{x}_{2}{\log \left(\frac{\left\lfloor t\right\rfloor}{t}\right) \: dt}\geq -\int^{x}_{2}{\frac{\{t\}}{t - \{t\}} \: dt} \geq -\int^{x}_{2}{\frac{1}{t-1} \: dt} = -\log (x-1) \geq -\log x.$
Finally,
$0 \geq \int^{2}_{1}{\log\left(\frac{\left\lfloor t\right\rfloor}{t}\right) \: dt} = -\int^{2}_{1}{\log t \: dt} = -2\log 2 - 2.$

It wouldn't be very linear of me to use the fact that $\sum_{n \leq x}{1/n} = O(\log x)$ , as I prove in the next section that
$\sum_{n \leq x}{\frac{1}{n}} = \log x + \gamma + O\left(\frac{1}{x}\right)$
though admittedly my proof is independent of the above result.

Ahmad · « **Reply #166 on:** November 25, 2009, 01:48:34 pm »

Quote from: /0 on November 25, 2009, 01:37:22 pm

Lagrange multipliers? Calculus is boss!

(*runs away to hide*)

I actually tried Lagrange multipliers on this question, it works. And it's not as ugly as it usually is.

TrueTears · « **Reply #167 on:** November 25, 2009, 03:43:37 pm »

Heh another way to prove the RHS inequality without the substitution:

$xy+yz+xz-2xyz=\frac{1}{4}(1-2x)(1-2y)(1-2z)+\frac{1}{4}$ .

Applying AM-GM on $(1-2x)(1-2y)(1-2z)$ yields:

$(1-2x) + (1-2y) + (1-2z) \ge 3((1-2x)(1-2y)(1-2z))^{\frac{1}{3}}$

Since $xy+yz+xz - 2xyz$ is positive this means $(1-2x)(1-2y)(1-2z)$ must all be positive or at least 2 of them is negative and 1 is positive.

Thus AM-GM can be applied.

$\implies \frac{3-2(x+y+z)}{3} \ge ((1-2x)(1-2y)(1-2z))^{\frac{1}{3}}$

$\therefore \frac{1}{27} \ge (1-2x)(1-2y)(1-2z)$ (since $x+y+z = 1$ )

Subbing this upper bound back yields $\left(\frac{1}{4}\right)\left(\frac{1}{27}\right) + \frac{1}{4} = \frac{7}{27}$

Thus $yz+zx+xy-2xyz \le \frac{7}{27}$

TrueTears · « **Reply #168 on:** November 25, 2009, 05:57:58 pm »

Quote from: TrueTears on November 24, 2009, 06:49:36 pm

3) Show that $\sqrt{a_1^2 + b_1^2} + \sqrt{a_2^2 + b_2^2} + ... + \sqrt{a_n^2 + b_n^2} \ge \sqrt{(a_1+a_2+...+a_n)^2 + (b_1+b_2+...+b_n)^2}$ for all real values of the variables. Furthermore, give a condition for equality to hold.

Well good ol' induction solves this pretty well. (Thanks Ahmad xD)

Base case:

Let $n = 2$

$\sqrt{a_1^2+b_1^2} + \sqrt{a_2^2+b_2^2} \ge \sqrt{(a_1+a_2)^2+(b_1+b_2)^2}$

$(a_1^2+b_1^2) + 2\sqrt{(a_1^2+b_1^2)(a_2^2+b_2^2)} + (a_2^2+b_2^2) \ge (a_1+a_2)^2 + (b_1+b_2)^2$

$2\sqrt{(a_1^2+b_1^2)(a_2^2+b_2^2)} \ge a_1^2+2a_1a_2+a_2^2 + b_1^2+2b_1b_2+b_2^2 - a_1^2-b_1^2-a_2^2-b_2^2$

$2\sqrt{(a_1^2+b_1^2)(a_2^2+b_2^2)} \ge 2a_1a_2+2b_1b_2$

$(a_1^2+b_1^2)(a_2^2+b_2^2) \ge (a_1a_2+b_1b_2)^2$

Which is true because of Cauchy-Schwarz.

Inductive Hypothesis:

Assume the inequality is true for $n = k$

$\sqrt{a_1^2 + b_1^2} + \sqrt{a_2^2 + b_2^2} + ... + \sqrt{a_k^2 + b_k^2} \ge \sqrt{(a_1+a_2+...+a_k)^2 + (b_1+b_2+...+b_k)^2}$

is true.

Proof:

Need to prove it's true for $n = k+1$

$\sqrt{a_1^2 + b_1^2} + \sqrt{a_2^2 + b_2^2} + ... + \sqrt{a_{k+1}^2 + b_{k+1}^2} \ge \sqrt{(a_1+a_2+...+a_{k+1})^2 + (b_1+b_2+...+b_{k+1})^2}$

So let's add $\sqrt{a_{k+1}^2 + b_{k+1}^2}$ to our inductive hypothesis.

This yields:

$\sqrt{a_1^2 + b_1^2} + \sqrt{a_2^2 + b_2^2} + ... + \sqrt{a_k^2 + b_k^2} + \sqrt{a_{k+1}^2 + b_{k+1}^2} \ge \sqrt{(a_1+a_2+...+a_k)^2 + (b_1+b_2+...+b_k)^2} + \sqrt{a_{k+1}^2 + b_{k+1}^2}$

Now if we can show $\sqrt{(a_1+a_2+...+a_k)^2 + (b_1+b_2+...+b_k)^2} + \sqrt{a_{k+1}^2 + b_{k+1}^2} > \sqrt{(a_1+a_2+...+a_{k+1})^2 + (b_1+b_2+...+b_{k+1})^2}$

Then we have completed the proof.

Let $a_1+a_2+...+a_k = u$ and $b_1+b_2+...+b_k = q$

Thus the inequality becomes $\sqrt{u^2+q^2} + \sqrt{a_{k+1}^2+b_{k+1}^2} > \sqrt{(u+a_{k+1})^2+(q+b_{k+1})^2}$

$u^2+q^2 + 2\sqrt{(u^2+q^2)(a_{k+1}^2+b_{k+1}^2)} + a_{k+1}^2+b_{k+1}^2 > u^2+2ua_{k+1}+a_{k+1}^2+q^2+2qb_{k+1}+b_{k+1}^2$

$2\sqrt{(u^2+q^2)(a_{k+1}^2+b_{k+1}^2)} > 2(ua_{k+1}+qb_{k+1})$

$(u^2+q^2)(a_{k+1}^2+b_{k+1}^2) > (ua_{k+1}+qb_{k+1})^2$

Which is true by Cauchy-Schwarz.

Thus $\sqrt{a_1^2 + b_1^2} + \sqrt{a_2^2 + b_2^2} + ... + \sqrt{a_n^2 + b_n^2} \ge \sqrt{(a_1+a_2+...+a_n)^2 + (b_1+b_2+...+b_n)^2}$

/0 · « **Reply #169 on:** November 25, 2009, 07:13:29 pm »

Very nice TT,

For Q2,

$10^6-(10^6-1) = (\sqrt{10^6}-\sqrt{10^6-1})(\sqrt{10^6}+\sqrt{10^6-1})$

$\sqrt{10^6} - \sqrt{10^6-1} = \frac{1}{\sqrt{10^6}+\sqrt{10^6-1}}$

So our problem is reduced to finding the number closest to $\sqrt{10^6}+\sqrt{10^6-1}\approx 2\sqrt{10^6} = 2000$

I'm not very rigorous sorry lol...

Ahmad · « **Reply #170 on:** November 25, 2009, 07:35:40 pm »

I think it'd be great if we could have some combinatorics problems in here! Why? Simply put they require very little knowledge beyond knowing when to add, subtract, multiply and divide and they're a great way to improve at problem solving. (Only a suggestion, sorry if I'm ruining your thread TT

)

kamil9876 · « **Reply #171 on:** November 25, 2009, 08:09:25 pm »

Yeah. It's one of my favourite topics in problem solving, along with number theory (especially when mixed together with number theory). We had quite a few nice ones in the other threads as well as one somewhere earlier in the thread

I did this one recently and think it is really nice: "Prove that the number of ways of writing n as a sum of consecutive natural numbers is equal to the number of odd divisors(greater than 1) of n"

TrueTears · « **Reply #172 on:** November 25, 2009, 09:52:30 pm »

Quote from: /0 on November 25, 2009, 07:13:29 pm

Very nice TT,

For Q2,

$10^6-(10^6-1) = (\sqrt{10^6}-\sqrt{10^6-1})(\sqrt{10^6}+\sqrt{10^6-1})$

$\sqrt{10^6} - \sqrt{10^6-1} = \frac{1}{\sqrt{10^6}+\sqrt{10^6-1}}$

So our problem is reduced to finding the number closest to $\sqrt{10^6}+\sqrt{10^6-1}\approx 2\sqrt{10^6} = 2000$

I'm not very rigorous sorry lol...

Thanks /0 xD

Quote from: Ahmad on November 25, 2009, 07:35:40 pm

I think it'd be great if we could have some combinatorics problems in here! Why? Simply put they require very little knowledge beyond knowing when to add, subtract, multiply and divide and they're a great way to improve at problem solving. (Only a suggestion, sorry if I'm ruining your thread TT )

Yeap, I'm moving onto combinatorics very soon, just gonna finish off the last exercise in algebra chapter and then combinatorics ftw!

zzdfa · « **Reply #173 on:** November 25, 2009, 10:58:18 pm »

Yeh Combinatorics is fun because there are lots of different ways to think about things. I like interpreting equations.

e.g. show that $\frac{\binom{2n}{n} \binom{2m}{m} }{\binom{n+m}{m}}$ is integer for all integer n,m.

and solution to kamil's problem:

suppose p*q=n , with q odd.

then $n=\underbrace{p+\cdots+p}_{\mathrm{q\,\,times}}$

do reverse gaussian pairing around the middle on the above, e.g:

2+2+2+2+2+2+2 -> -1+0+1+2+3+4+5

get rid of all the negatives in the equation by adding them to their positive counterparts : -1+0+1+2+3+4+5 -> 2+3+4+5

You can check that if $q\neq q'$ then we will get different sums:
denote the maximum number in the sum generated by q as m(q):
m(q)=n/q+(q-1)/2
m(q')=n/q'+(q'-1)/2

bit of algebra and we find that m(q)=m(q') iff q=q' or qq'=2n. but odd*odd=odd so the only choice is q=q'.

so we have that every odd divisor gives rise to a unique sum.

and i can't be bothered doing the other way (sum gives rise to unique odd divisor), it's pretty much the same anyway.

TrueTears · « **Reply #174 on:** November 25, 2009, 11:00:03 pm »

lol you guys make combinatorics sound so fun, I seriously can't wait now =.=

kamil9876 · « **Reply #175 on:** November 25, 2009, 11:26:34 pm »

ah yeah very nice one. I did it by representing the integer as a rectangle, ie the product. Then defined a function for each rectangle that would change it into a desired shape. And of course, we had to prove this function is one to one and each rectangle and desired shape is accounted for and all those other details(a bijection). The picture helped me find the mapping, but yes I realised that to change it into something that I can communicate online, it would be best to make an argument such as yours, which turns out analogous in certain aspects.

Also, the reason why the factor 1 is excluded is because the mapping for such a rectangle will map a 1*n rectangle to itself, hence it will be a sum of "one consecutive number"

TrueTears · « **Reply #176 on:** November 25, 2009, 11:27:25 pm »

Let $x = \sqrt{10^6} + \sqrt{10^6-1}$

Thus $\frac{1}{x} = \sqrt{10^6} - \sqrt{10^6-1}$

We can approximate $1999 < x < 2000$ (Since $\sqrt{10^6-1} \approx 1000$ )

Reciprocate the inequality yields:

$\frac{1}{2000} < \frac{1}{x} < \frac{1}{1999}$

This means $n = 2000$ or $n = 1999$

Let's assume $n = 2000$

This means $\frac{1}{2000}$ is closer to $\frac{1}{x}$ than $\frac{1}{1999}$

Which implies: $\frac{1}{x} - \frac{1}{2000} < \frac{1}{1999} - \frac{1}{x}$

$\frac{2}{x} < \frac{3999}{(2000)(1999)}$

$\frac{1}{x} < \frac{3999}{(4000)(1999)}$

$\sqrt{10^6} - \sqrt{10^6-1} < \frac{3999}{(4000)(1999)}$

$10^6 - 2(10^3)\sqrt{10^6-1} + 10^6-1 < \left(\frac{3999}{(4000)(1999)}\right)^2$

$2\left[10^6 - 10^3\sqrt{10^6-1}\right] < \left(\frac{3999}{(4000)(1999)}\right)^2 + 1$

We can approximate $\left(\frac{3999}{(4000)(1999)}\right)^2 \approx \left(\frac{4000}{(4000)(2000)}\right)^2$

Which is almost negligible small. Almost $0$ .

Thus $10^6 - 10^3\sqrt{10^6-1} < \frac{1}{2}$

$10^6 - \frac{1}{2} < 10^3\sqrt{10^6-1}$

The RHS is almost $10^6$ (it is just a bit less)

While the LHS is smaller than $10^6$ by $\frac{1}{2}$

This means the inequality holds.

Therefore $\frac{1}{2000}$ is closer to $\frac{1}{x}$ than $\frac{1}{1999}$

So $n = 2000.$

TrueTears · « **Reply #177 on:** November 26, 2009, 12:06:17 am »

~~1. Prove that $n! < \left(\frac{n+1}{2}\right)^n$ for $n = 2,3,4...$~~

~~2. Show that $\frac{1}{\sqrt{4n}} \le \left(\frac{1}{2}\right)\left(\frac{3}{4}\right) ...\left(\frac{2n-1}{2n}\right) < \frac{1}{\sqrt{2n}}$~~

3. Let $a_1, a_2 ... a_n$ be a sequence of positive numbers. Show that for all positive $x$

$(x+a_1)(x+a_2)...(x+a_n) \le \left(\frac{a_1+a_2+...+a_n}{n} + x\right)^n$

kamil9876 · « **Reply #178 on:** November 26, 2009, 01:19:29 am »

consider the sequence:

1,2,3,4.....n

it's arithmetic mean is $\frac{\sum_{i=1}^{n}i}{n}=\frac{n+1}{2}$

It's geometric mean is: $(n!)^{\frac{1}{n}}$

GM<AM by AM-GM. From which the result follows.

I noticed this inequality has been used many times in this thread, I love this pic btw, saw it in a textbook(a better version tho

)

kamil9876 · « **Reply #179 on:** November 26, 2009, 01:56:23 am »

q3.)

consider the sequence of $(x+a_1), (x+a_2).... (x+a_n)$ do some AM-GM.

Search the forums now!

We have moved!

Author Topic: TT's Maths Thread (Read 118808 times) Tweet Share

humph

Re: TT's Maths Thread

Ahmad

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

/0

Re: TT's Maths Thread

Ahmad

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

zzdfa

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

Recent Posts

User:
Password: