Induction (2 Viewers)

Lukybear · Feb 28, 2010

Use Induction to prove statement true for all positive integers n

$\frac{1}{n} \leq 1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n} - ln\ n \leq 1$

Hence show that

$e * e^{\frac{1}{2}}*e ^{\frac{1}{3}}...*e^{\frac{1}{n}}$

does not converge to a limit

shaon0 · Feb 28, 2010

Lukybear said:
Use Induction to prove statement true for all positive integers n

$\frac{1}{n} \leq 1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n} - ln\ n \leq 1$

Hence show that

$e * e^{\frac{1}{2}}*e ^{\frac{1}{3}}...*e^{\frac{1}{n}}$

does not converge to a limit

S(n): 1/n =< (1+...+1/n)-ln(n)

Base case is trivial

Assume, 1/k =< (1+...+1/k)-ln(k)

Let n=k+1:
LHS=(1+...+1/k+(1/(k+1)))-ln(k+1)
=1/k+ln(k)+1/(k+1)-ln(k+1)
=(1/k+1/(k+1))+ln(k/(k+1))
>=1/(k+1)
Additionally, 1/k, 1/(k+1) and ln(k/(k+1)) <1 for k<1
Thus, LHS=<1

1/n =< (1+...+1/n)-ln(n)
ln(n) =< (1+...+1/(n-1))
n =< e^(1+...+1/(n-1))
e1.e2...e(1/(n-1)) >= n
lim n-> inf LHS = lim n->inf RHS
e1.e2...=inf
Hence, doesn't converge

I think you can also use this to prove that the harmonic sum doesn't converge.
Also, idk if my solution's correct as i haven't written anything down so don't rage if my solution's incorrect.

Lukybear · Mar 1, 2010

hmmm... question is inequality? How did you sub into equn to make LHS =

Also, perhaps more importantly, how did you get final greater then 1/(k+1)

+

how did you also get result of <=1, since k>=1

Lukybear · Mar 1, 2010

bump?

shaon0 · Mar 1, 2010

Lukybear said:
hmmm... question is inequality? How did you sub into equn to make LHS =

Also, perhaps more importantly, how did you get final greater then 1/(k+1)

+

how did you also get result of <=1, since k>=1

1) I get confused with left and right very often. Sorry it should be RHS.
2) Do you agree that...1/k and ln(k/(k+1)) are positive for all k: k>=1? This can be verified by using the derivative and proving the functions are positive for k>=1 but decreasing.
So, 1/k+ln(k/(k+1)) >= 0 [Adding 1/(k+1) to both sides]
1/k+1/(k+1)+ln(k/(k+1)) >= 1/(k+1)
RHS >= 1/(k+1)
3) Since 1/k, 1/(k+1) and ln(k/(k+1)) are positive but decreasing functions for k>=1. Use derivatives and show that f'<0 for k>=1 where f is any of the above functions. And for the functions above i'm pretty sure max/turning pt occurs at k=1 and the functions are decreasing after k=1.
Note k=1 is base case...hopefully.

Trebla · Mar 1, 2010

First we need to derive a useful result.

$$Note that for the curve $y=\frac{1}{x}$ in the domain $k\leq x \leq k+1$ the area under the curve lies between the area of the upper rectangle and the lower rectangle (see HSC 2009 Q8 (b) for a similar type question or draw a diagram to see this). Hence$\\\\\frac{1}{k+1}\leq \int_k^{k+1}\frac{dx}{x}\leq \frac{1}{k}\\\\\Rightarrow \frac{1}{k+1}\leq \ln \left ( \frac{k+1}{k} \right )\leq \frac{1}{k}$

Now to proceed to the induction problem:

$$Should be obvious statement holds for $n = 1\\\\$Assume the truth of the statement for $ n = k\\\\\frac{1}{k} \leq 1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k} - \ln k \leq 1\\\\$Required to prove the statement holds for $n=k+1\\\\\frac{1}{k+1} \leq 1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k+1} - \ln(k+1) \leq 1\\\\$We know that $\\\\1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k}+\frac{1}{k+1} - \ln(k+1)\\\\=1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k} - \ln k - \ln(k+1)+\ln k+\frac{1}{k+1}\\\\\geq\frac{1}{k}- \ln(k+1)+\ln k+\frac{1}{k+1}\quad($by assumption$)\\\\=\frac{1}{k}+\frac{1}{k+1}+\ln\left ( \frac{k}{k+1} \right )\\\\$But $\frac{1}{k}-\ln\left ( \frac{k+1}{k} \right )\geq 0\quad ($as proven above$)\\\\$So $\frac{1}{k}+\ln\left ( \frac{k}{k+1} \right )\geq 0\\\\\Rightarrow \frac{1}{k}+\frac{1}{k+1}+\ln\left ( \frac{k}{k+1} \right ) \geq \frac{1}{k+1}\\\\\therefore \frac{1}{k+1} \leq 1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k+1} - \ln(k+1)$

$$Also $\\\\1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k}+\frac{1}{k+1} - \ln(k+1)\\\\=1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k} - \ln k - \ln(k+1)+\ln k+\frac{1}{k+1}\\\\\leq 1 - \ln(k+1)+\ln k+\frac{1}{k+1}\quad($by assumption$)\\\\=1+\frac{1}{k+1}+\ln\left ( \frac{k}{k+1} \right )\\\\$But $\frac{1}{k+1}-\ln\left ( \dfrac{k+1}{k} \right )\leq 0\quad($as proven above$)\\\\$So $ \frac{1}{k+1}+\ln\left ( \dfrac{k}{k+1} \right )\leq 0\\\\\Rightarrow 1+\frac{1}{k+1}+\ln\left ( \dfrac{k}{k+1} \right )\leq 1\\\\\therefore 1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k}+\frac{1}{k+1} - \ln(k+1) \leq 1\\\\$The statement holds for $n=k+1$ if it holds for $n=k$. Since it holds for $n=1$ then by induction it holds true for all integers $n$

Trebla · Mar 1, 2010

NOTE:

$\ln \left ( \frac{k}{k+1} \right )<0$

It is NOT positive, because

$\frac{k}{k+1}<1$

When you apply a logarithm to a number between 0 and 1, the output is negative.

As for the second part of the question:

$\frac{1}{n} \leq 1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n} - \ln n \leq 1\\\\$Exponentiate all sides$\\\\e^{\frac{1}{n}}\leq e^{1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n} - \ln n}\leq e\\\\e^{\frac{1}{n}}\leq e^{1}e^{\frac{1}{2}}e^{\frac{1}{3}}....e^{\frac{1}{n}}e^{- \ln n}\leq e\\\\e^{\frac{1}{n}}\leq \frac{1}{n}e^{1}e^{\frac{1}{2}}e^{\frac{1}{3}}....e^{\frac{1}{n}}\leq e\\\\ne^{\frac{1}{n}}\leq e^{1}e^{\frac{1}{2}}e^{\frac{1}{3}}....e^{\frac{1}{n}}\leq ne\quad(n>0)\\\\$as $n \rightarrow \infty$ the both sides of the inequality do not converge, hence $ e^{1}e^{\frac{1}{2}}e^{\frac{1}{3}}....e^{\frac{1}{n}} $ does not converge to a limit.$

(Not too sure about the argument for this one though)

Lukybear · Mar 1, 2010

Trebla said:
First we need to derive a useful result.

$$Note that for the curve $y=\frac{1}{x}$ in the domain $k\leq x \leq k+1$ the area under the curve lies between the area of the upper rectangle and the lower rectangle (see HSC 2009 Q8 (b) for a similar type question or draw a diagram to see this). Hence$\\\\\frac{1}{k+1}\leq \int_k^{k+1}\frac{dx}{x}\leq \frac{1}{k}\\\\\Rightarrow \frac{1}{k+1}\leq \ln \left ( \frac{k+1}{k} \right )\leq \frac{1}{k}$

Now to proceed to the induction problem:

$$Should be obvious statement holds for $n = 1\\\\$Assume the truth of the statement for $ n = k\\\\\frac{1}{k} \leq 1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k} - \ln k \leq 1\\\\$Required to prove the statement holds for $n=k+1\\\\\frac{1}{k+1} \leq 1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k+1} - \ln(k+1) \leq 1\\\\$We know that $\\\\1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k}+\frac{1}{k+1} - \ln(k+1)\\\\=1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k} - \ln k - \ln(k+1)+\ln k+\frac{1}{k+1}\\\\\geq\frac{1}{k}- \ln(k+1)+\ln k+\frac{1}{k+1}\quad($by assumption$)\\\\=\frac{1}{k}+\frac{1}{k+1}+\ln\left ( \frac{k}{k+1} \right )\\\\$But $\frac{1}{k}-\ln\left ( \frac{k+1}{k} \right )\geq 0\quad ($as proven above$)\\\\$So $\frac{1}{k}+\ln\left ( \frac{k}{k+1} \right )\geq 0\\\\\Rightarrow \frac{1}{k}+\frac{1}{k+1}+\ln\left ( \frac{k}{k+1} \right ) \geq \frac{1}{k+1}\\\\\therefore \frac{1}{k+1} \leq 1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k+1} - \ln(k+1)$

$$Also $\\\\1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k}+\frac{1}{k+1} - \ln(k+1)\\\\=1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k} - \ln k - \ln(k+1)+\ln k+\frac{1}{k+1}\\\\\leq 1 - \ln(k+1)+\ln k+\frac{1}{k+1}\quad($by assumption$)\\\\=1+\frac{1}{k+1}+\ln\left ( \frac{k}{k+1} \right )\\\\$But $\frac{1}{k+1}-\ln\left ( \dfrac{k+1}{k} \right )\leq 0\quad($as proven above$)\\\\$So $ \frac{1}{k+1}+\ln\left ( \dfrac{k}{k+1} \right )\leq 0\\\\\Rightarrow 1+\frac{1}{k+1}+\ln\left ( \dfrac{k}{k+1} \right )\leq 1\\\\\therefore 1+ \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{k}+\frac{1}{k+1} - \ln(k+1) \leq 1\\\\$The statement holds for $n=k+1$ if it holds for $n=k$. Since it holds for $n=1$ then by induction it holds true for all integers $n$

That is qutie skilled Trebla. How did you manage to get this? What thought processes did you use?

Also, not quite sure about ur first assumption. I do get how the area is between 2 rectangles. But why is then the area between
1/k+1 and 1/k

Also, for the second part of Q. I do not get how you get 1/ne^... for middle of inequality. e^-lnn is e^1/n?

Lukybear · Mar 1, 2010

shaon0 said:
1) I get confused with left and right very often. Sorry it should be RHS.
2) Do you agree that...1/k and ln(k/(k+1)) are positive for all k: k>=1? This can be verified by using the derivative and proving the functions are positive for k>=1 but decreasing.
So, 1/k+ln(k/(k+1)) >= 0 [Adding 1/(k+1) to both sides]
1/k+1/(k+1)+ln(k/(k+1)) >= 1/(k+1)
RHS >= 1/(k+1)
3) Since 1/k, 1/(k+1) and ln(k/(k+1)) are positive but decreasing functions for k>=1. Use derivatives and show that f'<0 for k>=1 where f is any of the above functions. And for the functions above i'm pretty sure max/turning pt occurs at k=1 and the functions are decreasing after k=1.
Note k=1 is base case...hopefully.

but ln(k/k+1) is not positive

shaon0 · Mar 1, 2010

Lukybear said:
but ln(k/k+1) is not positive

Yeah realised that after writing that up. But i don't think it matters.
ln(k+1)>ln(k)
1/k+ln(k+1)>ln(k)
1/k>ln(k/(k+1))
1/k-ln(k/(k+1))>0
1/k+ln(1+(1/k))>0

Trebla · Mar 1, 2010

Lukybear said:
Also, not quite sure about ur first assumption. I do get how the area is between 2 rectangles. But why is then the area between
1/k+1 and 1/k

Also, for the second part of Q. I do not get how you get 1/ne^... for middle of inequality. e^-lnn is e^1/n?

If you draw a diagram of the hyperbola y = 1/x for k < x < k + 1, both the lower and upper rectangle have a length of 1. The lower rectangle (which understates the true area) has a width of 1/(k + 1) which is the y-value corresponding to x = k + 1 and the upper rectangle (which overstates the true area) has a width of 1/k. Hence the area of the lower rectangle is 1/(k+1) and the area of the upper rectangle is 1/k.

This result was needed because we need to somehow prove that 1/k + ln(k/(k+1)) was non-negative and 1/(k + 1) + ln(k/(k+1)) was non-positive. Since ln (k/(k+1)) is actually negative, it's not that simple. Playing around with the inequality that is required to complete the proof sort of helps and knowing how to prove the limit result for e (which involves taking this result into further rearrangement) sort of led to that path.

Also,
e^{-ln n} = e^{ln (1/n)} = 1/n

Lukybear · Mar 1, 2010

Thxs so much for help guys. Very much appreciated.

Induction (2 Viewers)

Lukybear

Active Member

shaon0

...

Lukybear

Active Member

Lukybear

Active Member

shaon0

...

Trebla

Administrator

Trebla

Administrator

Lukybear

Active Member

Lukybear

Active Member

shaon0

...

Trebla

Administrator

Lukybear

Active Member

Users Who Are Viewing This Thread (Users: 0, Guests: 2)