How do I complete this proof by induction?

Question

Prove by induction that $u_n>\frac{1}{2}$ $∀n∈\mathbb{N}$ ; given $u_{n+1}=\frac{u_n^2+1}{u_n+2}$ and $u_1=1$.

(Where $\mathbb{N}=${$1,2,3,...$})

Let $P_n$ be the statement to be proved.

The base case is when $n=1$;

$P_1:$ $u_1=1>\frac{1}{2}$

$∴ P_1$ is true.

Now assume that for some n=k;

($P_k$) $u_k>\frac{1}{2}$ $:k∈ \mathbb {N}$

This is the inductive hypothesis.

Now we aim to prove that;

$u_{k+1}>\frac{1}{2}$

(Given the inductive hypothesis.)

$u_{k+1}=\frac{u_n^2+1}{u_n+2}$

$u_{k+1}-\frac{1}{2}=u_k-\frac{5}{2}+\frac{5}{u_k+2}$

Now;

$u_k>\frac{1}{2}$ $\implies \frac{5}{u_k+2}>2$ $∧$ $u_k-\frac{5}{2}>-2$

I set things up so that I could prove that $u_{k+1}-\frac{1}{2}>0$ but I don't know what to do after this last step. Did I make a mistake?

Answer 1

We have the recurrence:

$$ u_{n + 1} = \frac{u_n^2 + 1}{u_n + 2} $$

where $u_1 = 1$ and would like to prove $u_n > \frac{1}{2}$, $\forall n \in \mathbb{N}$. This is equivalent to proving $u_n - \frac{1}{2} > 0$, $\forall n \in \mathbb{N}$. We do so using induction. We first rewrite the recurrence:

$$ u_{n + 1} - \frac{1}{2} = \frac{u_{n}^2 + 1}{u_n + 2} - \frac{1}{2} = u_n - \frac{5u_n}{2u_n + 4} $$

Now we assume $u_n - \frac{1}{2} > 0$ and apply induction:

$$ u_{n + 1} - \frac{1}{2} = u_n - \frac{5u_n}{2u_n + 4} > 0 $$ $$ u_n > \frac{5u_n}{2u_n + 4} $$ $$ 1 > \frac{5}{2u_n + 4}$$ $$ 2u_n + 4 > 5$$ $$ u_n - \frac{1}{2} > 0 $$

We have that $u_1 = 1$ so the base case holds and so we conclude $u_n > \frac{1}{2}$, $\forall n \in \mathbb{N}$.

Answer 2

Hint:

You want to prove $u_{k+1}>\frac12$, which is equivalent (Per construction of $u_k$) to $\frac{u_k^2+1}{u_k+2}>\frac12$. But (assuming $u_k+2>0$) this is equivalent to $2(u_k^2+1)>u_k+2$. Knowing that $u_k>\frac12$, can you prove that $2(u_k^2+1)>u_k+2$, and thus prove that $u_{k+1}>\frac12$?

I think the mistake you made is trying to prove that $u_{k+1}-\frac12>0$ instead of $2u_{k+1}>1$.

Answer 3

I think I finally got it. I didn't make a mistake but it seems it was too early to use the inductive hypothesis. Using it after adding the two fractions completes the inductive step;

$u_{k+1}-\frac{1}{2}=u_k-\frac{5u_k}{2u_k+4}$

and since $u_k>\frac{1}{2}\implies \frac{5u_k}{2u_k+4}>\frac{1}{2}$, subtracting this from the inductive hypothesis proves that $u_{k+1}-\frac{1}{2}>0$

Edit: Subtracting inequalities like this is invalid. Instead, a correct approach is in the comments to this answer by prcssngnr.