# Proof by induction, inequality

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 8 '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 8 '17 at 22:24
• Can you check my method 1 again? I made an edit. – mathnoob123 Apr 8 '17 at 22:27
• I see no changes thus yet... though egreg seems to be editing at the moment. – Simply Beautiful Art Apr 8 '17 at 22:30
• Okay, edit is complete. Can you check now? I replaced $\ g(n)$ with $\ g(n+1)$ – mathnoob123 Apr 8 '17 at 22:34

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.

• 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 8 '17 at 22:30
• @FaiqRaees To prove monotonicity you only need to check that $f'(x)>0$ on $[1,+\infty)$. – OnoL Apr 8 '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 8 '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 8 '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 8 '17 at 22:39

$$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$$

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.