I have this straightforward induction problem that perhaps I am over thinking at this time of the morning. Here it is:
$U_1(x) = 1, \; U_2(x) = 2x, \; U_{n+1}(x) = 2x U_n(x) - U_{n-1}(x).$ Prove that $U_n(\cos{\theta}) = \frac{\sin{(n+1)\theta}}{\sin{\theta}}.$
I figure induction is the obvious way (and only way?) to go, so I'd like to show that $$U_{n+1}(\cos{\theta}) = \frac{\sin{(n+2)\theta}}{\sin{\theta}},$$ given that $$U_n(\cos{\theta}) = \frac{\sin{(n+1)\theta}}{\sin{\theta}}.$$
So I see immediately that I have a relation for $U_{n+1},$ meaning I'd have to show, $$\frac{\sin{(n+2)\theta}}{\sin{\theta}} = 2\cos{\theta}\frac{\sin{(n+1)\theta}}{\sin{\theta}} - U_{n-1}(\cos{\theta}).$$
The first time through, I went along blindly and said $U_{n-1}(\cos{\theta}) = \frac{\sin{n\theta}}{\sin{\theta}},$ changed things to complex exponentials and the relationship works out just fine. Then I got to thinking, am I allowed to use $U_{n-1}(\cos{\theta}) = \frac{\sin{n\theta}}{\sin{\theta}}$ in the first place? Or is this assuming what I am trying to prove?
More generally the question is, when proving something by induction, we typically assume it holds for $n,$ and have to show it holds for $n+1.$ Are we allowed to assume any knowledge about the $n-1$ term? I feel like that is assuming what we try to show, because with a change of index $n$, we would be assuming that it holds for $n$ and $n+1.$ Am I just overthinking this, or is there a more correct way to prove this?
to prove that $U_n (cos\theta)=\frac{sin((n+1)\theta)}{sin\theta} $ by induction need to verify that this is true for some $U_{n_0}$ and $U_{n_0 + 1}$ and $U_{n_0 +2}$, then to assume that the formula for $U_m$ is true for all $m\leq n $ and show that this is true also for $n + 1$.
so must check that $U_3(cos\theta)=2(cos\theta)U_2(cos\theta)-U_1(cos\theta)$ ie $\frac{sin(3\theta)}{sin\theta}=4cos\theta^2-1$ (I think that is correct, else we can not to prove the result). the second step: we assume that $U_{n-2}=\frac{sin((n-1)\theta)}{sin\theta}$, $U_{n-1}=\frac{sin(n\theta)}{sin\theta}$, $U_n(cos\theta)=2(cos\theta )U_{n-1}(cos\theta)-U_{n-2}(cos\theta)$ and to schow $U_{n}=\frac{sin((n+1)\theta)}{sin\theta}$.