Prove that the sequence $C_{n+1} = 1 + \frac{C_n}{C_n + 1}$ is monotonically increasing by induction

Question

I have a sequence

$$C_{n+1} = 1 + \frac{C_n}{C_n + 1}$$

With a base case $C_1 = 3/2$ and want to prove that it's monotonically increasing by induction.

Whenever I try to prove $C_n < C_{n+1} \implies C_{n+1} < C_{n+2}$

where $$C_{n+2} = 1 + \frac{2C_n + 1}{3C_n + 2} $$

I get to the inequality $$ \frac{C_n}{C_n + 1} < \frac{2C_n + 1}{(C_n + 1)^2} $$

but don't know how to get to the point where that implies that $C_{n+1} < C_{n+2}$

Thank

Answer 1

By induction, it is clear that $C_n>0$ for all $n$. Put $c=C_n$.

You want : $C_{n+1}\gt C_n$, which is equivalent to

$$ \begin{array}{lcl} C_{n+1}\gt C_n & \Leftrightarrow & 1+\frac{C_n}{C_n+1} \gt C_n \\ & \Leftrightarrow & 1+\frac{c}{1+c} \gt c \\ & \Leftrightarrow & \frac{1+2c}{1+c} \gt c \\ & \Leftrightarrow & 1+2c \gt c+c^2 \\ & \Leftrightarrow & 0 \gt -1-c+c^2 \\ & \Leftrightarrow & 0 \gt \big(c-\frac{1}{2}\big)^2-\frac{5}{4}\\ & \Leftrightarrow & \frac{5}{4} \gt \big(c-\frac{1}{2}\big)^2\\ & \Leftrightarrow & \frac{-\sqrt{5}}{2} \lt c-\frac{1}{2} \lt \frac{\sqrt{5}}{2}\\ & \Leftrightarrow & \frac{1-\sqrt{5}}{2} \lt c \lt \frac{1+\sqrt{5}}{2}\\ \end{array} $$

Put $\alpha=\frac{1-\sqrt{5}}{2}$ and $\beta=\frac{1+\sqrt{5}}{2}$. So, the goal is now to show that $\alpha \lt C_n \lt \beta$ for every $n$.

Can you finish from here ? (use induction and $C_{n+1}=2-\frac{1}{1+C_n}$).

Answer 2

Or you can set $f(x)=1+\dfrac{x}{x+1}$. Using the derivative prove that $f'>0$ and so $f$ is strictly increasing. Then apply $f$ to the induction hypothesis: suppose $C_{n}> C_{n-1}$, then $f(C_{n})> f(C_{n-1})$ because $f$ is increasing. Then conclude...

Answer 3

Or you can set $f(x)=1+\dfrac{x}{x+1}$. Using the derivative prove that $f'>0$ and so $f$ is strictly increasing. Then apply $f$ to the induction hypothesis: suppose $C_{n}>C_{n-1}$, then $f(C_{n})>f(C_{n-1})$ because $f$ is increasing. Then conclude...

Answer 4

As $C_1=\frac 32$, it is clear that every consecutive term $C_2, C_3, \dots, C_n$ is positive as $C_{n+1}$ is the sum of two positive terms for all $n>0$. We have

\begin{align}C_{n+2}-C_{n+1}&=\Big(1 + \frac{C_{n+1}}{C_{n+1} + 1}\Big) - \Big(1- \frac{C_n}{C_n + 1}\Big)\\&= \Big(1 + \frac{1 + \frac{C_n}{C_n + 1}}{2 + \frac{C_n}{C_n + 1}}\Big) - \Big(1- \frac{C_n}{C_n + 1}\Big)\\&= \Big(1 + \frac{2C_n+1}{3C_n+2}\Big) - \Big(1- \frac{C_n}{C_n + 1}\Big)\\&= \frac{2C_n+1}{3C_n+2}+\frac{C_n}{C_n + 1}\\&>0 \end{align}

which shows that $C_{n+2}>C_{n+1}$.

Answer 5

rewrite as $$C_{n+1} = 1 + \frac{C_n}{C_n + 1}= \frac{2C_n+1}{C_n + 1}=2-\frac{1}{1+C_n}$$ now $$C_{n+2} -C_{n+1}=2-\frac{1}{1+C_{n+1}}-(2-\frac{1}{1+C_{n}})=\\ \frac{1}{1+C_{n}}-\frac{1}{1+C_{n+1}}= \\\frac{1+C_{n+1}-(1+C_{n})}{(1+C_{n+1})(1+C_{n})}=\\ \frac{C_{n+1}-C_{n}}{(1+C_{n+1})(1+C_{n})}=$$so now you can build your induction $$ C_{n+1}>C_n \implies C_{n+2} > C_{n+1}$$because $$C_{n+2} -C_{n+1}=\frac{C_{n+1}-C_{n}}{(1+C_{n+1})(1+C_{n})}=\frac{C_{n+1}-C_{n}}{(positive)(positive)}$$

Answer 6

If $C_n\ge0$, then obviously $C_{n+1}\ge 1$. Furthermore, note that with $\phi=\frac{1+\sqrt5}2$, the Golden Ratio, $$ \begin{align} C_{n+1}-\phi &=1-\phi+\frac{C_n}{C_n+1}\\ &=-\frac1\phi+\frac{C_n}{C_n+1}\\ &=\frac{(\phi-1)C_n-1}{\phi(C_n+1)}\\ &=\frac{C_n-\phi}{\phi^2(C_n+1)} \end{align} $$ Thus, if $C_1\lt\phi$, then $C_n\lt\phi$ and $C_{n+1}\gt C_n$ for $n\ge1$.
Also, if $C_1\gt\phi$, then $C_n\gt\phi$ and $C_{n+1}\lt C_n$ for $n\ge1$.

If $C_1=\frac32\lt\phi$, then $C_n\lt\phi$ and $C_{n+1}\gt C_n$ for $n\ge1$ (increasing and bounded above).