Proof of recurrence relation with induction

Question

I have defined the following recurrence relation:

$$D(k+1) = 2D(k) + (-1)^{k+1}$$ with the base case D(1) = 1

I need help proving, through induction, that this relation is given by:

$$D(n) = \frac{1}{3} (2^{n+1} + (-1)^n) $$

Thank you!

Answer 1

The induction step hypothesis is $D(n) = \frac{1}{3} \left(2^{n+1} + (-1)^n\right)\,$. Then:

$$ \begin{align} D(n+1) & =2D(n)+(-1)^{n+1} && \quad\quad\quad \text{by the recurrence relation} \\ & = \frac{2}{3} \left(2^{n+1} + (-1)^n\right)+(-1)^{n+1} && \quad\quad\quad \text{by the induction hypothesis } \\ & = \frac{2}{3} \,2^{n+1} + \frac{2}{3} \cdot \frac{(-1)^{n+1}}{-1} +(-1)^{n+1} \\ & = \frac{1}{3} \,2^{n+2} + \left(1-\frac{2}{3}\right) \,(-1)^{n+1} \\ & = \frac{1}{3} \left( \,2^{n+2} + (-1)^{n+1} \right) && \quad\quad\quad \text{which proves the induction step}\\ \end{align} $$