# Using induction on a sequence

I have a problem where I am asked to use induction to show that for the sequence defined as $x_1=1$, $x_{n+1}=\frac{3x_n+4}{4}$ the upper bound is $<4$. I was thinking of a following way. Assume that for some $n+1$, $\frac{3x_n+4}{4} \geq 4$. Then we get $x_n \geq 4$. Repeating the process until we get to $x_1$, we get $x_1 \geq 4$, but it was defined to be equal to one, so we get a contradiction, thus the bound is indeed $<4$. However, I don't think this 'counts' as induction -- could you please show me an inductive way of approaching this problem? Many thanks!

Edit: I am thinking of the following: base case -- when n=1, we get $\frac{7}{4}$ which is less than 4. Now let's show that when this holds for $x_n$, it holds for $x_{n+1}$. $x_{n+1} = \frac{3x_n+4}{4} = 1 + \frac{3}{4} x_n$. But we know $x_n < 4$, so the whole expression must be less than 1+3=4. Is this a correct inductive approach?

-
Before assuming it's true for some $n$, show that it's true for $n=1$ (or $n=0$), even if it's trivial. edit: +1 for showing your thought process (: – Leonardo Fontoura Jun 11 '11 at 7:18
@confused: The first approach that you used is equivalent to the more standard induction of your second approach, and is sometimes a better way to think about the process. Sometimes the first process you used is called descent. It is logically equivalent to mathematical induction. I suggest you use standard induction for a while, until you have mastery of the process, and then prove things in whatever style is natural to you. – André Nicolas Jun 11 '11 at 9:06

The simplest thing to do is simply run the problem 'the other way' - can you show that if $x_n < 4$, then $x_{n+1} < 4$? Once you have that, induction will let you go 'from one to infinity'; since the statement is true for $x_1$, and since you've shown that if it's true for $x_n$ then it's true for $x_{n+1}$, you're then allowed to conclude by induction that it's true for all natural numbers $n$.

As for the so-called 'induction step' - showing that if the inequality is true for $x_n$, it's true for $x_{n+1}$ - you should be able to do that yourself, using just what you know about inequalities (a more specific hint: if $a < b$, then $(a+c) < (b+c)$; in addition, if $c > 0$, then $a\times c < b\times c$. These should be all that you need.)

Edit: Yes, the approach that you offer in your addendum is exactly what you're after! Nicely done.

-
Thanks a lot Steven! It suddenly made sense. – confused Jun 11 '11 at 7:22

It sounds like you have showed the implication $$x_{n+1}=\frac{3x_{n+1}+4}{4}\ge 4\Rightarrow x_n\ge4.$$

If you have shown this, then that should be enough (together with the initial test with $n=1$). The reason is that this implication is the contrapositive of the usual induction step. Normally in a proof by induction we show $P(n)\Rightarrow P(n+1)$ for some statement $P(n)$ defined for all natural numbers $n$. You hopefully remember that proving P$\Rightarrow$ Q is equivalent to proving 'not-Q' $\Rightarrow$ 'not-P'. Therefore it is rock solid logic to do the inductive step by showing 'not-$P(n+1)$' $\Rightarrow$ 'not-$P(n)$'.

We are free to prove the inductive step whichever way to see fit. It is still induction!

To address your second question. Perhaps you really wanted to prove the implication $$x_n<4\Rightarrow x_{n+1}=\frac{3x_n+4}{4}<4.$$ I'm fairly sure that if you managed to prove the claim above, then you can do this one as well. Either one of these implications gives you the inductive step. Pick whichever you prefer.

Then my inner nitpicking teacher wants to have a word with you, too. The claim seems to be to prove that for all positive integers $n$ we have the inequality $x_n<4$. It is an error to losely read this as saying `the sequence $x_n$ defined... has an upper bound $<4$'. If you say that a sequence (or a set) of numbers has an upper bound $<4$, that means that there exists a number $M<4$ such that $M$ is an upper bound to the sequence (or set), i.e. that the inequality $x_n\le M$ would be true for all $n$. In this case I dare say you would hard pressed to produce such an $M$. For extra credit I give you the exercise to show that while this sequence has $4$ as an upper bound, it has no upper bounds $<4$ :-)

-
@Jyrki: Hm, how about this: assume an upper bound $M=4-a$ exists. Then, for some n+1, $$\frac{3x_n+4}{4}=4-a.$$ Then, $$x_{n+2}=\frac{3(4-a)+4}{4}=4-\frac{3}{4}a,$$ which contradicts our assumption about M? – confused Jun 11 '11 at 7:41
You're on the right track. But $4-a$ could be an upper bound to the sequence even if $x_{n+1}\neq4-a$ for all $n$. Have you covered the concept of supremum (=the least upper bound) in your course? If not, then my question was a tad on the mean side. – Jyrki Lahtonen Jun 11 '11 at 7:50
@Jyrki, I thought I implied something stronger -- for the next x, I got $4-\frac{3}{4}a$, which is greater than $4-a$ (unless I am missing something), so any $M=4-a$ can't be an upper bound. And no, I just started reading the textbook for real analysis on my own, this is the first chapter. – confused Jun 11 '11 at 7:53
The problem in your logic is that $4-a$ may be an upper bound even if $x_n\neq 4-a$ for all $n$. The solution I was after in that extra credit problem starts with the contrapositive assumption that the least upper bound is $M=4-a<4$. Then $4-4a/3<M$, so $4-4a/3$ is not an upper bound. Hence $x_n>4-4a/3$ for some $n$. Then your logic shows that $x_{n+1}>4-a$, which means that $4-a$ was not an upper bound either. So the contrapositive is false, and the claim proven. – Jyrki Lahtonen Jun 11 '11 at 9:10
Yes. You are right. That would have worked equally well! – Jyrki Lahtonen Jun 11 '11 at 19:24