# Thread: Proof by induction and sequences

1. ## Proof by induction and sequences

The question goes...

Let the sequences $\displaystyle \{a_{n}\}$ and $\displaystyle \{b_{n}\}$ be defined by $\displaystyle a_{1}=1, b_{1}=1$,
$\displaystyle a_{n+1}=a_{n}+\frac{1}{n(n+1)}$ and $\displaystyle b_{n+1}=b_{n}+\frac{1}{(n+1)^2}$.
Prove by induction that $\displaystyle a_{n}=2-\frac{1}{n}$ and $\displaystyle b_{n}\leq a_{n}$. What is $\displaystyle \lim_{n\rightarrow\infty}a_{n}$? Prove that $\displaystyle \lim_{n\rightarrow\infty}b_{n}$ exists.

Can I have quite a detailed explanation please? I was never any good at proof by induction & I'm not too good at pure maths in general. Plus my lecturer's not been available for meetings lately

2. Hello,

Initialisation : $\displaystyle a_1=2-\frac{1}{1}=1$ true.

Then suppose that $\displaystyle a_n=2-\frac{1}{n}$.

$\displaystyle a_{n+1}=a_n+\frac{1}{n(n+1)}=2-\frac{1}{n}+\frac{1}{n(n+1)}=2-\frac{(n+1)-1}{n(n+1)}=2-\frac{1}{n+1}$

What ends the proof by induction.

Now, try to show by induction that $\displaystyle \forall n\in \mathbb{N}, b_n\le b_n$.

Then it is clear that $\displaystyle (b_n)$ increases and $\displaystyle \forall n\in \mathbb{N}, b_n\le a_n\le 2$ so $\displaystyle (b_n)$ converge.

3. why suppose that $\displaystyle a_{n}=2-\frac{1}{n}$?

4. It's the hypothesis of induction at rank n, and you show it stay true at rank n+1.

5. Okay. Still not 100% sure, but you're obviously right with your induction I still don't get the $\displaystyle b_{n}\leq a_{n}$ bit though.

6. Hello chella182
Originally Posted by chella182
Okay. Still not 100% sure, but you're obviously right with your induction I still don't get the $\displaystyle b_{n}\leq a_{n}$ bit though.
To prove this, note first that for $\displaystyle n>0, n(n+1)<(n+1)^2 \Rightarrow \frac{1}{n(n+1)}>\frac{1}{(n+1)^2}$

So for $\displaystyle n>0, a_n \ge b_n \Rightarrow a_n + \frac{1}{n(n+1)}\ge b_n + \frac{1}{n(n+1)} > b_n + \frac{1}{(n+1)^2}$

$\displaystyle \Rightarrow a_{n+1} > b_{n+1}$

And $\displaystyle a_1 = b_1$

So by induction $\displaystyle a_n \ge b_n,\, \forall n \ge 1$