Use Bonnet recursion formula to prove by induction

Question

Use Bonnet recursion formula: $P_{n+1}(x) = \frac{2n+1}{n+1} x P_n(x) - \frac{n}{n+1} P_{n-1}(x)$ to prove by induction

1) $P_n(1) = 1$ for all $n$

2) $P_n(-x) = (-1)^n P_n(x)$ for all $n$ an for all $x$

starting with $P_0(x) = 1$ and $P_1(x) = x$

I have done some induction proofs before, but for some reason I cannot get this to work out for me, any help would be much appreciated. Thanks for all the help in advance.

Answer 1

For $1$, you have to give a fixed $k$ such that $P_k(1) = 1$. I will assume that $P_0(1) = 1$. Then, suppose that for some positive integer $k$, $P_k(1) = 1$. Then $P_{k+1}(1) = \frac{2k+1}{k+1} (1)P_k(1) - \frac{k}{k+1}P_{k-1}(1) = \frac{2k+1}{k+1} - \frac{k}{k+1} = 1$.

2 is also not hard by induction. To make it a bit simpler, you can do seperate inductions based on the parity of $n$.

Answer 2

Hint: Use strong induction to prove the results. Assume the predicate holds for $n$ and $n-1$, and use it to prove true for $n+1$. For the base case, show true for $n=0, 1$.

Let's take the second result for example: $P_n(-x) = (-1)^n P_n(x)$

Base case:

$$\begin{array}{c|c} &\scriptsize{LHS}&\scriptsize{RHS}\\n & P_n(-x) & (-1)^nP_n(x)\\ \hline 0 & 1 & 1 \\ 1 & -x & -x\end{array}$$

Inductive step:

Assume true: $\begin{align}n: P_n(-x) & = (-1)^nP_n(x) \\ n-1: P_{n-1}(-x) & = (-1)^{n-1}P_{n-1}(x)\end{align}\tag{I}$

Then,

$\begin{align}n+1: P_{n+1}(-x) &= \frac{2n+1}{n+1}(-x)P_n(-x) - \frac{n}{n+1}P_{n-1}(-x) \\ &= \frac{2n+1}{n+1}(-x)\color{blue}{(-1)^nP_n(x)} - \frac{n}{n+1}\color{blue}{(-1)^{n-1}P_{n-1}(x)}\\ &= \frac{2n+1}{n+1}x(-1)^{n+1}P_n(x) - \frac{n}{n+1}(-1)^{n+1}P_{n-1}(x)\\&=(-1)^{n+1}\left(\frac{2n+1}{n+1}xP_n(x) - \frac{n}{n+1}P_{n-1}(x)\right)\\&=(-1)^{n+1}P_{n+1}(x) \text{ true}\end{align}$