1

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?

Merkh
  • 3,630
  • As a side for those who are interested, this relationship can be used to show that $\frac{2}{\pi}\int_{-1}^1 U_m U_n \sqrt{1 - x^2} ; dx = \delta_{nm}.$ I thought this made it a pretty neat problem. – Merkh Jun 07 '16 at 10:32
  • What you should use is not ordinary induction, rather strong induction, wherein by inductive hypothesis, $y$ is true, if it lies from the base case to $n$. So, $n-1$ is true by inductive hypothesis. – Roby5 Jun 07 '16 at 10:38
  • You are allowed to use $U_{n-1}(\cos{\theta}) = \frac{\sin{n\theta}}{\sin{\theta}}$ since you are given that the proposition holds for $n=1,2$ – mastrok Jun 07 '16 at 10:43
  • I see the difference. I guess my follow up question would have to be, if I am trying to be as rigorous as possible, would the proof be any different than the original other than stating that I am assuming the relationship holds for all $k = 1, ... , n?$ – Merkh Jun 07 '16 at 10:44
  • The proof will be along the same lines. See this. – Roby5 Jun 07 '16 at 10:46

1 Answers1

0

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

m.idaya
  • 1,558
  • Right, the question I posed was "Is it valid to assume $U_i(\cos{\theta}) = \frac{\sin{(i+1)\theta}}{\sin{\theta}}$ for all $i \leq n,$ in proving the $n+1$ case. The base case and general method is straightforward if we can do so, but my confusion was if we assume the $n$-th case and would like to show the $n+1$th case, wouldn't assuming the $n$-th and the $n-1$'th cases to be true be assuming what we would like to show in the first place? As it turns out, it is not, and now I know the difference (and equivalence) between induction and strong induction. – Merkh Jun 07 '16 at 12:54
  • it is essential to use a high induction as in the expression of $U_n$ involved two other words $U_{n-1}$ and $U_{n-2}$. I apologize for my English and i do not really understand your problem thank you – m.idaya Jun 07 '16 at 13:09