Proof by induction, inequality

Question

The sequence of real numbers $\ a_1,a_2,a_3.....$ is such that $\ a_1=1$ and $$a_{n+1} = \left(a_n+\frac{1}{a_n}\right)^{\!\lambda} $$ where $\ \lambda >1$

Prove by mathematical induction that for $n\geq 2$ $$a_n\geq2^{g(n)} $$ where $g(n) = \lambda^{n-1} $

Attempt

I have solved the base case. I am having a problem in proving the statement for $n+1$. I tried two methods. Here they are:

Method 1

Assuming inductive hypothesis to be true $$ a_n\geq2^{g(n)} $$ $$ a_n+\frac{1}{a_n}\geq2^{g(n)} $$ $$ \left(a_n+\frac{1}{a_n}\right)^{\!\lambda}\geq(2^{g(n)})^{\!\lambda}$$ $$ a_{n+1}\geq 2^{g(n+1)} $$

The statement holds true for $n+1$

Is this method correct?

Method 2 $$ a_{n+1}-2^{g(n)} =a_{n+1}-2^{g(n)} $$ $$ a_{n+1}-2^{g(n)} =\left(a_n+\frac{1}{a_n}\right)^{\!\lambda}-2^{g(n)} $$ $$ a_{n+1}-2^{g(n)} =\frac{(a^2_n+1)^\lambda}{a_n^\lambda}-2^{g(n+1)} $$ $$ a_{n+1}-2^{g(n)} =\frac{(a^2_n+1)^\lambda-(a_n^\lambda)(2^{g(n+1)})}{a_n^\lambda} $$ In this method, I don't know how to show $(a^2_n+1)^\lambda-(a_n^\lambda)(2^{g(n)})$ and $a_n^\lambda$ to be greater than or equal to $0$ which is necessary to prove the statement.

Can somebody provide me some hints which would prove beneficial in solving this problem?

In method 1, all you proved is that if $a_n\ge2^{g(n)}$, then $a_{n+1}\ge a_n\ge2^{g(n)}$, but you did not prove that $a_{n+1}\ge2^{g(n+1)}$ — Simply Beautiful Art, Apr 08 '17 at 22:23
Likewise, in the second proof, you start off with $a_{n+1}-2^{g(n)}$. Are you sure this is what you want? — Simply Beautiful Art, Apr 08 '17 at 22:24
I see no changes thus yet... though egreg seems to be editing at the moment. — Simply Beautiful Art, Apr 08 '17 at 22:30
Okay, edit is complete. Can you check now? I replaced $\ g(n)$ with $\ g(n+1) $ — mathnoob123, Apr 08 '17 at 22:34
So after this, I write "Since the statement $\ P(n) $ implies $\ P(n+1)$ for $\ n\geq 2$, my proof is complete right? And by the way, what do you mean by initial condition? — mathnoob123, Apr 08 '17 at 22:37
You need to check it holds true at, say, $n=2$, for the induction to begin. — Simply Beautiful Art, Apr 08 '17 at 22:40

score 1 · Accepted Answer · answered Apr 08 '17 at 22:27

1

Hint:

Step 1: Check that the conclusion holds for $n=1$ (which is immediate and necessary, but absent in your proof);

Step 2: Given that the conclusion holds for some $n\ge 1$ (i.e., $a_n\ge 2^{g(n)}$), show that it also holds for $n+1$, i.e., $a_{n+1}\ge 2^{g(n+1)}$. One way to show this is by first proving that the function $$f(x)=\left(x+\frac 1x\right)^\lambda$$ is strictly increasing when $x\ge 1$, which is not difficult. With this result, we will see that $$a_{n+1}=\left(a_n+\frac{1}{a_n}\right)^\lambda\ge \left(2^{g(n)}+2^{-g(n)}\right)^\lambda>2^{\lambda g(n)}=2^{g(n+1)}.$$ Completing the two steps yields the desired result.

answered Apr 08 '17 at 22:27

OnoL

2,685

The proof for the "increasing" part is we are adding a $\ \frac{1}{x} $ term which is smaller than 1 since x is greater than 1. Right? – mathnoob123 Apr 08 '17 at 22:30
@FaiqRaees To prove monotonicity you only need to check that $f'(x)>0$ on $[1,+\infty)$. – OnoL Apr 08 '17 at 22:35
@FaiqRaees In case you haven't learned calculus before, you can also get the monotonicity by picking $x>y\ge 1$ and proving $x+\frac 1x-y-\frac 1y=(x-y)(1-\frac{1}{xy})>0$. – OnoL Apr 08 '17 at 22:37
Yes but I only know how to find a derivative on a point, not on a whole range. Perhaps, can you show me how to do it for this problem? – mathnoob123 Apr 08 '17 at 22:38
@FaiqRaees Notice that in order to prove the monotonicity of $f(x)$, it suffices to prove the monotonicity of $x+\frac 1x$, because $g(y)=y^\lambda$ is known to be increasing when $x>0$ and $\lambda>0$. – OnoL Apr 08 '17 at 22:39
Oh okay got it. Thank you very much. – mathnoob123 Apr 08 '17 at 22:41
Can you help me with the second part of this question, or should I start a new thread? – mathnoob123 Apr 08 '17 at 22:52
@FaiqRaees What is the second part? – OnoL Apr 08 '17 at 23:16
http://math.stackexchange.com/questions/2225507/proving-an-inequality – mathnoob123 Apr 08 '17 at 23:17

score 0 · Answer 2 · answered Apr 08 '17 at 22:32

$$a_{n+1} > 2^{g(n)}$$ The statement holds true for $n+1$

Correct, but it is not the statement you are after. You need to show that $$a_{n+1} > 2^{g(n+1)}$$

Assuming $a_n > 2^{\lambda^{n-1}}$ we have $$a^{n+1} = \left(a_n + \frac{1}{a_n}\right)^{\lambda} > a_n^{\lambda} > \left({{2^\lambda}^{n-1}}\right)^\lambda = \left(2^\lambda\right)^n$$

score 0 · Answer 3 · answered Apr 08 '17 at 22:40

Method 1

You're on the right track, but you're forgetting some bits along the road.

Suppose $a_n\ge 2^{g(n)}$. Then $a_n+\dfrac{1}{a_n}\ge 2^{g(n)}$ as well, so $$ a_{n+1}=\left(a_n+\frac{1}{a_n}\right)^{\!\lambda} \ge (2^{g(n)})^{\lambda}=2^{\lambda g(n)} $$ Now $\lambda g(n)=\lambda\cdot \lambda^{n-1}=\lambda^n=g(n+1)$.

The missing step is checking the statement for $n=2$, that is $$ a_2\ge 2^{g(2)}=2^\lambda $$ But, by definition, $$ a_2=(1+1)^\lambda=2^{\lambda} $$

Method 2

You seem to be trying to show that $a_{n+1}-2^{g(n+1)}\ge0$, but you're starting from the wrong direction.

Proof by induction, inequality

3 Answers3