How is the statement $a_n \ge \frac{1}{2}$ proved by induction for the sequence $a_{n+1}=\frac{1}{3}(a_n+1)$ with $a_1=1$?

Conditions

• The sequence is defined by $a_{n+1}=\frac{1}{3}(a_n+1)$ for $n \ge 1$.
• The initial value is $a_1=1$.
• The goal is to prove $a_n \ge \frac{1}{2}$ for all $n \ge 1$.

Reasoning, step by step

1. Verify the base case: $a_1=1$, and since $1 \ge \frac{1}{2}$, the statement holds for $n=1$.
2. State the inductive hypothesis: Assume $a_n \ge \frac{1}{2}$ for some $n \ge 1$.
3. Apply the recurrence relation: $a_{n+1}=\frac{1}{3}(a_n+1)$.
4. Substitute the inductive hypothesis into the inequality: $a_{n+1} \ge \frac{1}{3}(\frac{1}{2}+1)$.
5. Simplify the right side: $\frac{1}{3}(\frac{3}{2}) = \frac{1}{2}$.
6. Conclude that $a_{n+1} \ge \frac{1}{2}$, completing the inductive step.

Example

The board writes: "Suppose $a_n \ge \frac{1}{2}$" followed by the implication $a_{n+1}=\frac{1}{3}(a_n+1) \ge \frac{1}{3}(\frac{1}{2}+1) = \frac{1}{2}$.

Common misconceptions

• Assuming the inductive step proves the statement for $n=1$ instead of $n+1$.
• Forgetting that the function $f(x) = \frac{1}{3}(x+1)$ is increasing, which justifies substituting the lower bound.

Watch the explanation

Explore next

• Why does the lecturer say the sequence must be bounded and monotone?
• What does the lecturer say must be shown after proving the sequence is bounded from below?