Home » Blog » Another proof by mathematical induction

Another proof by mathematical induction

If a_1, a_2, a_3, \ldots is a sequence of real numbers with a_i > 0 for all i, and if c is a fixed real number with c > 0, such that

    \[ a_n \leq ca_{n-1} \qquad \text{for all } n \geq 2 \]

prove by induction that

    \[ a_n \leq a_1 c^{n-1} \qquad \text{for all } n \geq 1. \]

Proof. First, for the case n=1, we have a_1 on the left, and on the right we have a_1 c^0 = a_1. Hence, the inequality (which is not strict) holds for this case.
Assume then that the inequality holds for some integer k \in \mathbb{Z}_{>0}. Then, we have

    \begin{align*}  &&a_k &\leq a_1 c^{k-1}\\ \implies && ca_k &\leq a_1 c^k & (\text{Multiplying by } c)\\ \implies && a_{k+1} & \leq a_1 c^k & (a_{k+1} \leq ca_k \text{ by assumption}). \end{align*}

Thus, the statement holds for all n. \qquad \blacksquare

Point out an error, ask a question, offer an alternative solution (to use Latex type [latexpage] at the top of your comment):