Let $a_{1} = 2$ and let $a_{n+1} = \frac{1}{2}(a_{n} + 3)$ for all n ≥ 1. Prove that for all positive integers n, $a_{n} = 3 − \frac{1}{2^{n−1}}$.

Question

I have this problem that I need to prove through mathematical induction, however I been having trouble figuring this out. I basically get stuck in the induction step because I am not sure what to do next to prove P(k+1).

My attempt:

Base Case: We show P(1) holds: On the left hand we have $a_{1} = 2$ and on the right we have $3 − \frac{1}{2^{1−1}} = 2$. Therefore P(1) holds.

Induction Step: Assume that P(k): $a_{k} = 3 - \frac{1}{2^{k−1}}$ is true, then we show that P(k+1): $a_{k+1} = 3 - \frac{1}{2^{k}}$ is true.

Firstly am I doing the Base Case and Induction Step correctly(without showing P(K+1) part)? Secondly how can I go by showing P(k+1)? Because I believe I need to tie it in with the sequence. Any help would be appreciated.

Answer 1

You're on the right track. Just write out $a_{k+1}$, use the inductive hypothesis, and expand: $$a_{k+1} = \frac{1}{2}(a_k+3) = \frac{1}{2}\left(3-\frac{1}{2^{k-1}}+3\right) = \frac{1}{2}\left(6-\frac{1}{2^{k-1}}\right).$$ Can you take it from there?

Answer 2

Here is a direct proof without using induction:

$$a_n-\frac{1}{2}a_{n-1}=\frac{3}{2}$$ $$\frac{1}{2}a_{n-1}-\frac{1}{4}a_{n-2}=\frac{3}{2}\times\frac{1}{2}$$ $$\cdots$$ $$2^{-(n-2)}a_2-2^{-(n-1)}a_1=\frac{3}{2}\times 2^{n-2}$$ Therefore $$a_n-2^{-(n-1)}a_1=\frac{3}{2}\times(1+2+\cdots+2^{n-2})$$ $$a_n-2^{-(n-1)}\times 2=\frac{3}{2}\frac{1-\frac{1}{2^{n-1}}}{1-1/2}$$ $$a_n-2^{-(n-2)}=3-\frac{3}{2^{n-1}}$$ $$a_n=3-\frac{1}{2^{n-1}}$$