Induction on a sequence {$a_n$}

Question

Let a sequence be defined by $a_0=1$ and $a_{n+1}=\sqrt{3a_n+4}$. Prove by inductions that $0\le a_n \le 4$ for all n.

For some reason I can't figure out what my hypothesis is? I know my base case is $a_0$ but then what do I assume? Do I isolate $a_n$? Any answers to these questions or hints would be appreciated!

Your initialisation would be $a_0\le4$, which is true. The induction hypothesis is $a_n\le4$, which you then need to use to prove that $a_{n+1} = \sqrt{3a_n+4}\le4$. — Marc, Feb 24 '16 at 17:43

score 1 · Accepted Answer · answered Feb 24 '16 at 17:50

Base case:

For $n=0$, we have $a_0=1$, thus $1 \le a_0 \le 4$.

Thus the statement is true for $n=0$.

Induction Hypothesis:

Let the statement be true for some $n=k$, where $k\ge0$ and $k \in \mathbb Z$.

Then, we have $$1\le a_k \le 4$$

Inductive Step:

Consider now for $n=k+1$. From the given recurrence relation, we have

$$a_{k+1}=\sqrt{3a_k + 4}$$ Using the inductive hypothesis, $$1\le a_k \le 4$$ $$3\le 3a_k \le 12$$ $$7\le 3a_k + 4 \le 16$$ $$\sqrt7\le \sqrt{3a_k + 4} \le \sqrt{16}$$ $$1<\sqrt7\le \sqrt{3a_k + 4} \le 4$$ $$1\le a_{k+1} \le 4$$

Thus, whenever the statement is true for $n=k$, it is also true for $n=k+1$.

Using the principle of mathematical induction, it is true for all $n\ge0$, $n\in \mathbb Z$

Induction on a sequence {$a_n$}

1 Answers1