# Thread: Proof By Induction

1. ## Proof By Induction

Can somone show me how to lay out an answer for this question:

The sequence of real numbers $u_1, u_2, u_3,$ ... is such that $u_1 = 5.2$ and $u_{n+1} = \frac{6u_n +10}{u_n +3}$. Prove by induction that $u_n>5$, for ne+.

2. Hello

Originally Posted by Air
Can somone show me how to lay out an answer for this question:

The sequence of real numbers $u_1, u_2, u_3,$ ... is such that $u_1 = 5.2$ and $u_{n+1} = \frac{6u_n +10}{u_n +3}$. Prove by induction that $u_n>5$, for ne+.
Hmm what do you think of that :

$u_{n+1}=\frac{6u_n+10}{u_n+3}=6-\frac{8}{u_n+3}$

(you can do the basis and set up the induction hypothesis, right ? if not, just ask)

3. Originally Posted by Moo
Hello

Hmm what do you think of that :

$u_{n+1}=\frac{6u_n+10}{u_n+3}=6-\frac{8}{u_n+3}$

(you can do the basis and set up the induction hypothesis, right ? if not, just ask)
Induction hypothesis?

My teacher said for these question the layout is important to get someone to understand the proof so can you also show how you would lay out an answer for this?

4. $u_1=5.2>5$, so the inequality stands for n=1.
Now, suppose $u_n>5$ and we have to prove that $u_{n+1}>5$
$u_{n+1}-5=\frac{6u_n+10}{u_n+3}-5=\frac{u_n-5}{u_n+3}>0$
Then $u_{n+1}>5$.
Thus $u_n>5, \ \forall n\geq 1$

5. Originally Posted by Air
Induction hypothesis?

My teacher said for these question the layout is important to get someone to understand the proof so can you also show how you would lay out an answer for this?
Ok, there are three main steps in an induction proof

Preliminary : state the induction property.

$u_n>5 \quad \forall n \in \mathbb{Z}^+$
This is mostly for yourself, to clear out the view.

1st step : the basis.
You have to check that this is true for the very first term. Here, because we are working on $\mathbb{Z}^+$, it will be $u_1$.
Is $u_1>5$ ? Yes. So the basis is verified.

2nd step : the inductive step.
Induction hypothesis : assume that the property is true for a rank n.
--> $u_n>5$

Then, prove that if this is verified for a rank n, it will be for the following rank, n+1.

--> Using the hypothesis that $u_n>5$, prove that $a_{n+1}>5$

In most of the induction exercises, this proof will require you to go back to the recursive definition of $u_n$

------------
Is it clear ?

6. Originally Posted by Moo
Is it clear ?
Yes!

Thank you!

7. Basis :
$u_1=5.2 > 5$
Hence the basis is verified

Inductive step :
Let's assume that $u_n>5$. And let's prove that $u_{n+1}>5$.

\begin{aligned} u_{n+1} &=\frac{6u_n+10}{u_n+3} \\
&=\frac{6u_n+18-8}{u_n+3} \\
&=6-\frac{8}{u_n+3} \end{aligned}

$u_n>5 \implies u_n+3 >8 \implies \frac{1}{u_n+3}<\frac 18 \implies \frac{-8}{u_n+3}>-1$

$\implies u_{n+1}=6-\frac{8}{u_n+3}>6-1 \implies u_{n+1}>5 \ \square$

So the inductive hypothesis is verified, hence the property is true for all $n \in \mathbb{Z}^+$

-----------------

This is how I was taught to write in a test

8. Originally Posted by Moo

$u_n>5 \implies u_n+3 >8 \implies \frac{1}{u_n+3}<\frac 18 \implies \frac{-8}{u_n+3}>-1$
$u_n>5 \implies u_n+3 >8$

How did get get that? ^

9. Originally Posted by Air
$u_n>5 \implies u_n+3 >8$

How did get get that? ^
Adding both sides by 3 o.O

10. Another question (Prove by induction):

$\sum^n_{r=1} r2^r = 2[1+(n-1)2^n]$

I did (but ended up at a dead end):

Originally Posted by Myself
Let $n=1$

$\therefore \sum^1_{r=1} (1)2^{(1)} = 2[1+((1)-1)2^{(1)}]$

$LHS=2; RHS=2 \therefore$ true for $n=1$

Assume true for $n=k$

$\therefore \sum^k_{r=1} r2^r = 2[1+(k-1)2^k]$

Consider $n=k+1$

$\therefore \sum^{k+1}_{r=1} r2^r = 2[1+(k)2^{k+1}]$

$\equiv \sum^k_{r=1} r2^r + (k+1)$

$\therefore = 2[1+(k-1)^{2k}] + k+1$

$\therefore = 2+2(k-1)^{2k} + (k+1)$

$\therefore = 2+2[(k-1)^k]^2 + (k+1)$
Can I have help on how to alter it to correct proof? ^

11. Unfortunately, I can't quote what you have quoted yourself

It's not really correct to write this :

$\sum^1_{r=1} (1)2^{(1)}$

Write $\sum_{r=1}^1 r2^r=(1)2^1=2$

And then your working
------------------------
For this line :
$
\therefore \sum^{k+1}_{r=1} r2^r = 2[1+(k)2^{k+1}]
$

say that this is what you want to prove. The therefore sign shouldn't be here, because you haven't proved it yet.
This should be in your draft paper, for that you can see what you have in mind, what result you should find.

------------------------
$\sum^{k+1}_{r=1} r2^r=\left(\sum^{k}_{r=1} r2^r \right)+(k+1){\color{red}2^{k+1}}$

But you had the good idea =)

$=2[1+(k-1)2^k]+(k+1)2^{k+1}$

$=\textbf{2}[1+(k-1)2^k]+(k+1) \cdot \textbf{2} \cdot 2^k$

Factoring it :

$=2 \left(1+(k-1)2^k+(k+1)2^k\right)$

Can you continue ?

Edit : another mistake, for this line

$\therefore = 2[1+(k-1)^{2k}] + k+1$
why did you put to the power 2k ? it was a multiplication by $2^k$, which is not the same ^^

12. Originally Posted by Moo

$=\textbf{2}[1+(k-1)2^k]+(k+1) \cdot \textbf{2} \cdot 2^k$
Why did you multiply by 2?

13. Originally Posted by Air
Why did you multiply by 2?
I didn't

I had $2^{k+1}$, so I made appear 2, in order to have a common factor with $\textbf{2}[1+(k-1)2^k]$.

$2^{k+1}=2^k \cdot 2^1=2 \cdot 2^k$

Is it clear for the other points ? ^^

14. Originally Posted by Moo
I didn't

I had $2^{k+1}$, so I made appear 2, in order to have a common factor.

$2^{k+1}=2^k \cdot 2^1=2 \cdot 2^k$

Is it clear for the other points ? ^^
Yes, its clear. The other 2 is just from the original series.

15. Originally Posted by Moo
Factoring it :

$=2 \left(1+(k-1)2^k+(k+1)2^k\right)$

Can you continue ?

I opened up the bracket :

$2(1+k2^k - 2^k +k2^k + 2^k)$

$2(1+2k2^k)$

?

Page 1 of 2 12 Last