Showing that a given recurrence relationship equals sin(nx) - please advise me how to come to a conclusion at the end?

Question

If, $u_{r}-2\cos\theta u_{r-1}+u_{r-2}=0$,

given $u_{0}=0$, $u_{1}=\sin \theta$, find $u_{n}$

My workings:

I rearranged to get, $u_{r}=2\cos\theta u_{r-1}-u_{r-2}$

Then starting with $r=2$,

$u_{2}=2\sin \theta \cos\theta \implies u_{2}=\sin (2\theta)$

For $r=3$,

$u_{3}=2\cos\theta u_{2}-u_{1}$

$\therefore u_{3}=2\cos\theta \cdot 2\sin \theta \cos\theta -\sin \theta$

$\therefore u_{3}=\sin \theta(4\cos^{2}\theta -1)$

$\therefore u_{3}=\sin (3\theta)$

For $r=4$,

$u_{4}=2\cos\theta u_{3}-u_{2}$

$\therefore u_{4}=2\cos\theta \sin \theta (4\cos^{2}\theta -1) - 2\cos\theta \sin \theta$

$\therefore u_{4}=\sin \theta [( 8\cos^{3}\theta - 2\cos\theta) - 2\cos\theta]$

$\therefore u_{4}=\sin \theta ( 8\cos^{3}\theta - 4\cos\theta)$

$\therefore u_{4}=\sin (4\theta)$

... and so on ...

My Conclusion: The pattern suggests that $u_{n}=\sin (n\theta)$

Is this a rigorous enough conclusion at school A-level? Or do I need to go further and use proof by induction? The question only says, find $u_{n}$.

Answer 1

Just having a pattern isn't enough to deduce what the sequence is, unless you actually prove it. You are correct that induction is the way to go:

Suppose $u_{n-1}=\sin({(n-1)\theta})$ and $u_n=\sin{(n\theta)}$ (true for $n=1$)

Then \begin{align*} u_{n+1}&=2\cos{\theta}\sin{(n\theta)}-\sin{((n-1)\theta)}\\ &=\cos{\theta}\sin{(n\theta)}+\cos{\theta}\sin{(n\theta)}-\left( \sin{(n\theta)}\cos{\theta}-\sin{\theta}\cos{(n\theta)} \right)\\ &=\cos{\theta}\sin{(n\theta)}+\sin{\theta}\cos{(n\theta)}\\ &=\sin{((n+1)\theta)} \end{align*} Now we have $u_{n}=\sin{(n\theta)}$ and $u_{n+1}=\sin{((n+1)\theta)}$ so we are done by induction.

I am assuming that at A-Level you are only allowed to use the induction where you say "if its true for $n$, then its true for $n+1$" or something to that effect. That is why we had to make the inductive assumption for two terms, as that is how many terms we require to get to the next $u_n$.

Answer 2

Here is an induction-free proof, although the trade-off is having to use complex numbers, generating functions, and partial fraction expansion.

Let $f(z,\theta)=\sum_{n=0}^{\infty}u_n(\theta)z^n$ be the generating function for the sequence $\{u_n\mid n\ge 0\}$. Multiply the recurrence relation through by $z^n$ and sum over $n\ge 2$ to obtain $$ (f(z,\theta)-0-z\sin\theta)-2\cos\theta (z(f(z,\theta)-0))+z^2f(z,\theta)=0. $$ Collecting like terms, we get $$ (1-2z\cos\theta+z^2)f(z,\theta)-z\sin\theta=0, $$ i.e. $$ f(z,\theta)=\frac{z\sin\theta}{1-2z\cos\theta+z^2}. $$ We want to decompose the denominator as $(1-a_{+}z)(1-a_{-}z)$ for some $a_{+},a_{-}$. It is easy to see that those are the reciprocals of the roots of $1-2z\cos\theta+z^2=0$, which are $\cos\theta\pm\sqrt{\cos^2\theta-1}=\cos\theta\pm i\sin\theta=e^{\pm i\theta}$, so their reciprocals are $e^{\mp i\theta}$. We want to write $f(z,\theta)$ as $$ f(z,\theta)=\frac{A_+}{1-e^{i\theta}z}+\frac{A_-}{1-e^{-i\theta}z}=\frac{(A_{+}+A_{-})-(A_{+}e^{-i\theta}+A_{-}e^{i\theta})z}{1-2z\cos\theta+z^2}, $$ from which we see that $A_{+}+A_{-}=0$ and $-(A_{+}e^{-i\theta}+A_{-}e^{i\theta})=\sin\theta$, so $A_{-}=-A_{+}$ and therefore $\sin\theta=A_{+}(e^{i\theta}-e^{-i\theta})=2iA_{+}\sin\theta$, from which we obtain $A_{\pm}=\pm\frac{1}{2i}$. Now, expanding both partial fractions as a geometric series, we get $$ f(z,\theta)=\sum_{n=0}^{\infty}\left(A_{+}e^{in\theta}+A_{-}e^{-in\theta}\right)z^n, $$ so $$ u_n(\theta)=A_{+}e^{in\theta}+A_{-}e^{-in\theta}=\frac{e^{in\theta}-e^{-in\theta}}{2i}=\sin(n\theta). $$

Answer 3

This recurrence can be read as

$$ u_r-\alpha u_{r-1}+u_{r-2}=0,\ \ \ u_0 = 1,\ u_1 = \sin\theta $$

so considering $u_r = c_0\gamma^r$ we have

$$ c_0(\gamma^r-\alpha\gamma^{r-1}+\gamma^{r-2})= c_0(\gamma^2-\alpha \gamma + 1)\gamma^{r-2}=0 $$

so we have

$$ u_r = c_1\left(\frac 12\left(\alpha-\sqrt{\alpha^2-4}\right)\right)^r+c_2\left(\frac 12\left(\alpha+\sqrt{\alpha^2-4}\right)\right)^r $$

but $\alpha = 2\cos\theta$ then

$$ u_r = c_1\left(\cos\theta-i\sin\theta\right)^r+c_2\left(\cos\theta+i\sin\theta\right)^r = c_1 e^{-ir\theta}+c_2e^{ir\theta} $$

and now imposing the initial conditions we have

$$ u_r = \sin(r\theta) $$

Answer 4

$\sin((n+1)x) =\sin(nx)\cos(x)+\cos(nx)\sin(x)\\ \sin((n-1)x) =\sin(nx)\cos(x)-\cos(nx)\sin(x)\\ $

Adding,

$\sin((n+1)x)+\sin((n-1)x) =2\sin(nx)\cos(x) $

so if $u_n=\sin(nx) $,

$u_{n+1}+u_{n-1} =2\cos(x)u_n $.

Similarly,

$\cos((n+1)x) =\cos(nx)\cos(x)-\sin(nx)\sin(x)\\ \cos((n-1)x) =\cos(nx)\cos(x)+\sin(nx)\sin(x) $

Adding,

$\cos((n+1)x)+\cos((n-1)x) =2\cos(nx)\cos(x) $

BTW, these are numerically stable ways to iteratively compute $\sin(nx)$ and $\cos(nx)$ and were used in the past.