# Proof by induction

Tags:
1. Apr 7, 2017

### Faiq

1. The problem statement, all variables and given/known data
The sequence of positive numbers $u_1,u_2,u_3...$ is such that $u_1<4$ and $u_{n+1}= \frac{5u_n+4}{u_n+2}$
i. By considering $4-u_{n+1}$, prove by induction that $u_1<4$ for $n\geq 1$
Mod note: The above is incorrect. In a later post the OP revised this to
3. The attempt at a solution
I have never been introduced to these types of backward induction so I am not aware of the statements I have to make and prove. I do get the general idea that it's like finding the limit of $4-u_{n+1}$ as $u_n \rightarrow 4$ and then say that since as the upper limit of the function is 0, then it must be smaller than 0. So it would be very helpful if I am given an outline on how to solve this.

Last edited by a moderator: Apr 8, 2017
2. Apr 7, 2017

### SammyS

Staff Emeritus
How is this "backward induction"?

It's induction, so first do the base case.

Use the suggestion: Consider $4-u_{2}$ .

3. Apr 8, 2017

### Faiq

I used the phrase "backward induction" in the sense that for a general induction problem we try to show that if a statement $P(n)$ can be converted into a $P(n+1)$ statement using allowed operations then the statement is true. Here we are supposed to use the concept in a reverse.

$$\ 4-u_{2}=4-u_{2}$$
$$\ 4-u_{2}=4- \frac{5u_1+4}{u_1+2}$$
$$\ 4-u_{2}=4-\frac{5+\frac{4}{u_1}}{1+\frac{2}{u_1}}$$
$$\ 4-u_{2}>4-\frac{5+1}{1+1/2}$$
$$\ 4-u_{2}>4-\frac{6}{3/2}$$
$$\ 4-u_{2}>0$$
$$\ 4>u_{2}$$
Is this correct? If yes what I have to do next?
And one more thing, Can I just use the given statement $u_1<4$ as my base case?

4. Apr 8, 2017

### nuuskur

How do you "use the concept in reverse"? The description you gave, $P(n)\Longrightarrow P(n+1)$ is The principle of induction (in $\mathbb N$ at least).

5. Apr 8, 2017

### Faiq

Well in most questions we try to convert the statement $P(n)$ into $P(n+1)$ but here aren't we trying to convert $P(n+1)$ into $P(n)$? If no, then probably my analogy is incorrect. Please guide me how to solve the remaining part.

Last edited: Apr 8, 2017
6. Apr 8, 2017

### nuuskur

Edit: nvm
You are used to induction working in the normal way, if it holds for $n$, then show it holds for $n+1$ and done. You can define induction however you like, though. You may induce for all even or odd numbers. You may induce "backwards" [though that's not really correct way to say it.]

What confused me is this bit: Show that for all $n\geq 1$ $u_1<4$?? How exactly does $u_1$ quantify with respect to $n$?

Last edited: Apr 8, 2017
7. Apr 8, 2017

### Faiq

Oh sorry that was a mistake.
The question is:
i. By considering$4−u_{n+1}$, prove by induction that $u_n<4$ for all $n\geq1$
Mod note: I have revised post #1 with this correction.

Last edited by a moderator: Apr 8, 2017
8. Apr 8, 2017

### nuuskur

A series is an infinite sum. You are talking about a sequence. It's important to make the distinction or you will confuse people.

The way I see it, your objective is to show by induction that for all $n\in\mathbb{N}$ $u_n<4$ and the base case is assumed to be solved according to your first post. Assume now that for some $n>1$ $u_n<4$ holds, then if you show $4-u_{n+1}>0$, you will have proven the result.

In #3, you solved the special case $n=2$.

9. Apr 8, 2017

### SammyS

Staff Emeritus
In that last step, you are assuming that if $\ u_1<4\$ then $\ \displaystyle 4-\frac{5+1}{1+1/2}>\frac{5+\frac{4}{u_1}}{1+\frac{2}{u_1}}\$.

While that is true, you have not demonstrated this..
I suggest picking up at your second line.
$\displaystyle\ 4-u_{2}=4- \frac{5u_1+4}{u_1+2}\$​
Combine the two terms on the right hand side into one rational expression, using a common denominator. You can then show that $\ u_2<4\$ and that $\ u_2>u_1\$, assuming that $\ u_1>0\$.

.

10. Apr 8, 2017

### Faiq

Earlier you said, "While that is true, you have not demonstrated this.." Can you tell me what do you mean by this? How am I supposed to demonstrate that? The question already says that $u_1<4$ so can I not just continue by saying "Assuming inductive hypothesis to be true" and then divide by $4$ instead of $u_1$

$$\ 4-u_{2}=4-\frac{5u_1+4}{u_1+2}$$
$$\ 4-u_{2}=\frac{4-u_1}{u_1+2}$$
Considering $u_n>0$ then

Now what I have to do?

Edit:
By the way, the question I typed is a little bit wrong
Instead of proving $u_1<4$, I have to prove $u_n<4$
Apologies.

The $5$ in the numerator was incorrectly written. Changed it to the correct $4$

Last edited: Apr 8, 2017
11. Apr 8, 2017

### nuuskur

You have to use your inductive assumption. Also, when you simplify, you get $4-u_2 = \frac{3-u_1}{u_1+2}$

12. Apr 8, 2017

### Faiq

So in the post where I proved for $n=2$, if I were to substitute $u_1$ by $u_n$ and $u_2$ by $u_{n+1}$, will the proof be valid?

13. Apr 8, 2017

### nuuskur

In any event for the special case, you could do something like this. Assume for a contradiction that $4-u_2\leq 0$, then
$$4-u_2 = \frac{4-u_1}{2+u_1} = 1-\frac{2-2u_1}{2+u_1}\leq 0$$
but then $u_1\leq 0$ which would contradict one of your assumptions in your first post. The general case follows similarly.

Last edited: Apr 8, 2017
14. Apr 8, 2017

### SammyS

Staff Emeritus
That looks good.

$u_1 \$ is positive so $\ u_1+2 \$ is also positive, thus $\ 4-u_2 >0 \$. Right ?

You can also show that $\ u_2>u_1 \$ .

15. Apr 8, 2017

### Faiq

It is actually $4-u_1$ in the numerator.

16. Apr 8, 2017

### Faiq

Okay perfect. What I have to do next?

17. Apr 8, 2017

### nuuskur

Yes, you are right. I copied the problem incorrectly from your first post :( The core idea of my post is the same, regardless.

Do the same for the general case. Assume $4-u_n>0$ for some $n$ and show it must be true that $4-u_{n+1}>0$.

18. Apr 8, 2017

### Faiq

I have not studied principles for contradictions in depth so I am confused here. You assume $4-u_2\leq 0$, a contradictory statement to be true. So any conclusions derived using this contradiction must be incorrect. So why are we treating the incorrect result to be a contradiction when it is itself an indirect proof that $4-u_1\geq0$

19. Apr 8, 2017

### Faiq

I have converted $4-u_n>0$ into $\frac{24}{u_n+2}-u_{n+1}>0$
I am not really sure what to do now. I know I can't use $u_n=4$ since that will make the left term smaller and the inequality might not hold true.

20. Apr 8, 2017

### nuuskur

When we have to prove $A\Longrightarrow B$, one possibility is to assume for a contradiction $B$ does not hold and consider $A\land\neg B$. If it yields a contradictory result, it means the assumption that $\neg B$ must be incorrect. Due to the excluded third principle, it can then only be that $B$ is true. The contradictions you could arrive at could be $A\land \neg B\Longrightarrow \neg A$, which is clearly a contradiction. You could also contradict one of your assumptions or some base axioms.I will walk through the example in case of $n=2$.

Let $4-u_1>0$. We want to show that
$$4-u_1>0\Longrightarrow 4-u_2 = \frac{4-u_1}{2+u_1}>0$$
Let's assume for a contradiction that $\frac{4-u_1}{2+u_1}\leq 0$. Then $u_1\leq 0$, which contradicts the fact that all elements in the sequence are positive numbers.

The validity of the statement is obvious, though and this sort of proof is overkill.