How can you prove this by strong induction?

Question

The sequence $b_1,b_2,...$ is defined recursively as:\begin{align} b_1&=0;\\ b_2&=1;\\ b_n&=2b_{n-1}-2b_{n-2}-1 \ \text{for} \ n\geq3. \end{align} Prove that this means: $$\forall n\geq1: b_n=(\sqrt{2})^n \sin{\left(\frac{1}{4}\pi n \right)}-1$$

Edit:

I have tried to prove this by strong induction and have verified than $P(1)$ and $P(2)$ is true, where $P(n)$ is the statement $b_n=(\sqrt{2})^n \sin{\left(\frac{1}{4}\pi n \right)}-1$.

edit: I have assumed that $P(k-2)$ and $P(k-1)$ is true for $k\in\mathbb{N}$. Then I have managed to simplify to: $$b_n=(\sqrt{2})^n \left[\sqrt{2}\sin{\left(\frac{1}{4}\pi (n-1) \right)}- \sin{\left(\frac{1}{4}\pi (n-2) \right)}\right]-5$$

I can't simplify any further.

Answer 1

Since you have verified the base case, we proceed to the inductive case. Fix $n >2$ and suppose that for all $k <n$, $P(k)$ is true. We want to show that $P(n)$ is true.

$$ \begin{aligned} b_{n}&=2b_{n-1}-2b_{n-2}-1\\ &=2\left((\sqrt{2})^{n-1}\sin\left(\frac{1}{4}\pi (n-1)\right)-1\right)-2\left((\sqrt{2})^{n-2}\sin\left(\frac{1}{4}\pi (n-2)\right)-1\right)-1\\ &=(\sqrt{2})^{n}\left(\sqrt{2}\sin\left(\frac{\pi (n-1)}{4}\right)-\sin\left(\frac{\pi (n-2)}{4}\right)\right) - 1 \end{aligned} $$

Now, using $\sin(A+B)=\sin A\cos B+\cos A\sin B$, we get

$$ \begin{aligned} &\sqrt{2}\sin\left(\frac{\pi (n-1)}{4}\right)-\sin\left(\frac{\pi (n-2)}{4}\right)=\\ &\sqrt{2}\left(\sin\left(\frac{\pi n}{4}\right)\cos\left(\frac{-\pi}{4}\right)-\cos\left(\frac{\pi n}{4}\right)\sin\left(\frac{-\pi}{4}\right)\right)-\sin\left(\frac{\pi n}{4}\right)\cos\left(\frac{-\pi}{2}\right)+\cos\left(\frac{\pi n}{4}\right)\sin\left(\frac{-\pi}{2}\right)\\ &=\sqrt{2}\left(\sin\left(\frac{\pi n}{4}\right)\frac{1}{\sqrt{2}}-\cos\left(\frac{\pi n}{4}\right)(\frac{-1}{\sqrt{2}})\right)-\cos\left(\frac{\pi n}{4}\right)\\ &=\sin\left(\frac{\pi n}{4}\right)+\cos\left(\frac{\pi n}{4}\right)-\cos\left(\frac{\pi n}{4}\right)\\ &=\sin\left(\frac{\pi n}{4}\right) \end{aligned} $$

Answer 2

Comment on the Approach in the Question

The inductive step needs to show $$ \begin{align} 2b_{n-1}-2b_{n-2}-1 &=2\left(2^{(n-1)/2}\sin\left(\tfrac{(n-1)\pi}4\right)-1\right)-2\left(2^{(n-2)/2}\sin\left(\tfrac{(n-2)\pi}4\right)-1\right)-1\\ &=2^{(n+1)/2}\sin\left(\tfrac{(n-1)\pi}4\right)-2^{n/2}\sin\left(\tfrac{(n-2)\pi}4\right)-1\\ &=2^{n/2}\left[\sqrt2\sin\left(\frac{n\pi}4\right)\cos\left(\frac\pi4\right)-\sqrt2\cos\left(\frac{n\pi}4\right)\sin\left(\frac\pi4\right)\right]\\ &-2^{n/2}\left[\sin\left(\frac{n\pi}4\right)\cos\left(\frac\pi2\right)-\cos\left(\frac{n\pi}4\right)\sin\left(\frac\pi2\right)\right]-1\\ &=2^{n/2}\sin\left(\frac{n\pi}4\right)-1\\[3pt] &=b_n \end{align} $$

---

A Different Approach

To solve $$ b_n=2b_{n-1}-2b_{n-2}-1\tag{1} $$ let $a_n=b_n+1$. Then $$ a_n=2a_{n-1}-2a_{n-2}\tag{2} $$ which has the characteristic polynomial $x^2-2x+2$, whose roots are $1\pm i$. Therefore, the solutions to $(2)$ are $$ a_n=\alpha(1+i)^n+\beta(1-i)^n\tag{3} $$ and the solutions to $(1)$ are $$ b_n=\alpha(1+i)^n+\beta(1-i)^n-1\tag{4} $$ To satisfy $b_1=0$ and $b_2=1$, we compute $\alpha=-\frac i2$ and $\beta=\frac i2$. Thus, we get $$ b_n=-\frac i2(1+i)^n+\frac i2(1-i)^n-1\tag{5} $$

---

Changing the Form

Starting from $(5)$, we get $$ \begin{align} b_n &=-\frac i2(1+i)^n+\frac i2(1-i)^n-1\\ &=\frac{e^{-i\pi/2}}22^{n/2}e^{in\pi/4}+\frac{e^{i\pi/2}}22^{n/2}e^{-in\pi/4}-1\\ &=2^{n/2}\cos\left(\frac{(n-2)\pi}4\right)-1\\ &=2^{n/2}\sin\left(\frac{n\pi}4\right)-1\tag{6} \end{align} $$