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

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}$$.

• "the question only says, find $u_n$" $\;$ You only found $u_2,u_3,u_4$, and just stating "and so on" doesn't count as a proof. You still have to prove it for $u_n$, by induction or otherwise. See also solving a linear recurrence relationship involving trig.
– dxiv
Commented May 28, 2023 at 7:49

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$$.

• Thank you for your opinion. I also thought that just having a pattern can't be enough.
– Nik
Commented May 28, 2023 at 8:23

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).$$

• Thank you for your contribution.
– Nik
Commented May 31, 2023 at 6:17

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)$$

• Thank you. This is a very interesting alternative method I would never have thought of.
– Nik
Commented Jun 4, 2023 at 6:41

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

$$\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)$$

$$\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.