Prove Induction: u_n < 4 for All n ≥ 1

[Faiq]

Homework Statement

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

i. By considering $4−u_{n+1}$, prove by induction that $u_n<4$ for all $n\geq1$

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.

 

[SammyS]

Homework Statement

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$

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.

How is this "backward induction"?It's induction, so first do the base case.

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

 

[Faiq]

How is this "backward induction"?It's induction, so first do the base case.

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

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.

Now to your suggestion,
$$\ 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?

 

[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).

 

[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.

 

[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$?

 

[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.

 

[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$.

 

[SammyS]

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.

Now to your suggestion,
$$\ 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} $$

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..

$$\ 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?

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\$.

.

 

[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$

 

[nuuskur]

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

 

[Faiq]

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

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?

 

[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.

 

[SammyS]

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} $$
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.

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 \$ .

 

[Faiq]

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{3-u_1}{2+u_1} = 1-\frac{1-2u_1}{2+u_1}\leq 0$$
but then $u_1\leq -\frac{1}{3}$ which would contradict one of your assumptions in your first post.

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

 

[Faiq]

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 \$ .

Okay perfect. What I have to do next?

 

[nuuskur]

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

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

Okay perfect. What I have to do next?

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$.

 

[Faiq]

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.

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$

 

[Faiq]

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$.

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.

 

[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.

 

[Faiq]

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.

Okay got it.

 

[nuuskur]

In the general case, you assume $4-u_n>0$ for some $n$. Then you look at $4-u_{n+1} = \frac{4-u_n}{2+u_n}$. The numerator is positive by inductive assumption and the demoninator is positive because of the assumption that all elements in the sequence are positive.

You might notice that I keep saying "..for some $n$.. ". You may equivalently set up your induction by proving the base case and then assuming that your statement holds for Every natural number $k<n$ and then proceed to demonstrate the validity in case $k=n$.

 

[Faiq]

Got it. Thank you very much.

 

[SammyS]

I realize that you have worked this out with @nuuskur , but I would like to pick up the conversation I was having with you.

Your reply in post #16 to my post in #14.

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 \$ .

perfect. What I have to do next?

Solving problems like this takes time for thought and time to investigate various methods of attack which may turn out to be useful (as well as others which might not be so useful for the problem at hand).

So, you ask what to do next. $\ \ \$ ( Before that, did you actually show that $\ u_2>u_1 \$? )

I would ask, what information about $\ u_1\$ did you use / need to show that $\ u_2>4 \$ and that $\ u_2 \$ is positive?

(Did you actually show that $\ u_2 \$ is positive? )​

Since you might not answer this, I'll supply those answers.

The fact that $\ u_1+2>0 \$ was sufficient to show that $\ u_2<4 \$ .

I used that $\ u_1 +2>1 \$ to show that $\ u_2>u_1 \$.

Clearly, if $\ u_1\$ is positive, then this shows that also, $\ u_2\$ is positive.​

The general inductive looks very much like the above base step.

If $\ u_k\$ is positive and $\ u_k<4\$ , then you get the result that $\ u_{k+1}\$ is positive and $\ u_{k+1}<4\$, the desired result​

... and now for that last question of yours in Post #3.

...
And one more thing, Can I just use the given statement $u_1<4$ as my base case?

This is the sort of issue which often requires doing some work on the problem, before it can be answered.

It should be apparent at this point, that you can use as the base case, $\ u_1\$ is positive and $\ u_1<4\$

Not only are other terms of the sequence also positive as a result, but the sequence is monotone increasing.
.

 

[Faiq]

I realize that you have worked this out with @nuuskur , but I would like to pick up the conversation I was having with you.

Your reply in post #16 to my post in #14.

Solving problems like this takes time for thought and time to investigate various methods of attack which may turn out to be useful (as well as others which might not be so useful for the problem at hand).

So, you ask what to do next. $\ \ \$ ( Before that, did you actually show that $\ u_2>u_1 \$? )

I would ask, what information about $\ u_1\$ did you use / need to show that $\ u_2>4 \$ and that $\ u_2 \$ is positive?

(Did you actually show that $\ u_2 \$ is positive? )​

Since you might not answer this, I'll supply those answers.

The fact that $\ u_1+2>0 \$ was sufficient to show that $\ u_2<4 \$ .

I used that $\ u_1 +2>1 \$ to show that $\ u_2>u_1 \$.

Clearly, if $\ u_1\$ is positive, then this shows that also, $\ u_2\$ is positive.​

The general inductive looks very much like the above base step.

If $\ u_k\$ is positive and $\ u_k<4\$ , then you get the result that $\ u_{k+1}\$ is positive and $\ u_{k+1}<4\$, the desired result​

... and now for that last question of yours in Post #3.

This is the sort of issue which often requires doing some work on the problem, before it can be answered.

It should be apparent at this point, that you can use as the base case, $\ u_1\$ is positive and $\ u_1<4\$

Not only are other terms of the sequence also positive as a result, but the sequence is monotone increasing.
.

You gave a great emphasis on proving the individual terms to be positive. However, the question itself stated that a sequence of positive integers. So can you tell me is it necessary to prove these statements even though the question mentions it? It just asks me to prove $u_n<4$. So do I also have to prove $u_n>0$ to fit the "positive integer sequence" description?