6
$\begingroup$

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?

  • 1
    @confu$s$ed: 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. $S$ometime$s$ 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.2011-06-11

2 Answers 2

3

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.

  • 1
    Thanks a lot Steven! It suddenly made sense.2011-06-11
2

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$ :-)

  • 1
    Yes. You are right. That would have worked equally well!2011-06-11