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?
Best Answer
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.