# Thread: Proof by induction and sequences

1. ## Proof by induction and sequences

The question goes...

Let the sequences $\{a_{n}\}$ and $\{b_{n}\}$ be defined by $a_{1}=1, b_{1}=1$,
$a_{n+1}=a_{n}+\frac{1}{n(n+1)}$ and $b_{n+1}=b_{n}+\frac{1}{(n+1)^2}$.
Prove by induction that $a_{n}=2-\frac{1}{n}$ and $b_{n}\leq a_{n}$. What is $\lim_{n\rightarrow\infty}a_{n}$? Prove that $\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 : $a_1=2-\frac{1}{1}=1$ true.

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

$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 $\forall n\in \mathbb{N}, b_n\le b_n$.

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

3. why suppose that $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 $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 $b_{n}\leq a_{n}$ bit though.
To prove this, note first that for $n>0, n(n+1)<(n+1)^2 \Rightarrow \frac{1}{n(n+1)}>\frac{1}{(n+1)^2}$

So for $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}$

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

And $a_1 = b_1$

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