# Induction proof concerning Pell numbers

Problem: The Pell numbers $p_n$ are defined by the recurrence relation \begin{align*} p_{n+1} = 2p_n + p_{n-1} \end{align*} for $n \geq 1$, together with $p_0 = 0$ and $p_1 = 1$.

Prove with mathematical induction that \begin{align*} p_{n+1} p_{n-1} - p_n^2 = (-1)^n \end{align*} for every $n \in \mathbb{N} \setminus \left\{0\right\}$.

Proof: Initial step: for $n = 1$ we have $p_2 p_0 - p_1^2 = (-1)$ which is true given the initial conditions.

Inductive step: Suppose the above expression is true for $n > 1$. Then we have to show that it is also true for $n + 1$. So we have \begin{align*} p_{n+1} p_{n-1} - p_n^2 = (-1)^n. \end{align*} I now plugged in the expression for $p_{n+1}$ given above, and thus got: \begin{align*} (2p_n + p_{n-1}) p_{n-1} - p_n^2 = (-1)^n, \end{align*} or \begin{align*} 2p_n p_{n-1} + p_{n-1}^2 - p_n^2 = (-1)^n. \end{align*}

I'm not sure if I'm doing this right, and I don't know how to proceed. Any help would be appreciated.

Look at what you want to show: you want to show that $p_{n+2}p_n-p_{n+1}^2=(-1)^{n+1}$. You know that $p_{n+2}=2p_{n+1}+p_n$, so this is equivalent to

$$(-1)^{n+1}=(2p_{n+1}+p_n)p_n-p_{n+1}^2=p_n^2+2p_np_{n+1}-p_{n+1}^2\;.\tag{1}$$

Your induction hypothesis is that $p_{n+1}p_{n-1}-p_n^2=(-1)^n$; that has a $p_{n-1}$ that isn’t present in $(1)$, so perhaps we should manipulate the target $(1)$ a bit more to get a $p_{n-1}$. We might apply $p_{n+1}=2p_n+p_{n-1}$ to one of the factors of $p_{n+1}$ in $p_{n+1}^2$ to get

\begin{align*} p_n^2+2p_{n+1}-p_{n+1}^2&=p_n^2+2p_{n+1}-p_{n+1}(2p_n+p_{n-1})\\ &=p_n^2+2p_np_{n+1}-2p_np_{n+1}-p_{n-1}p_{n+1}\\ &=p_n^2-p_{n-1}p_{n+1}\;. \end{align*}

Can you finish it from there?

• Thanks for your help, but I'm not sure if I can finish. I don't really know towards where I have to work. How did you get to the left-hand side of that equation, I mean: $p_n^2 - 2p_{n+1} - p_{n+1}^2$ ? Because that's not the same as the equation in (1). – Kamil Jan 27 '15 at 22:24
• @Kamil: Do the calculation that led to $(1)$: $p_{n+2}p_n-p_{n+1}^2$ is equal to $p_n^2+2p_np_{n+1}-p_{n+1}^2$. You want to show that $p_{n+2}p_n-p_{n+1}^2=(-1)^{n+1}$, so you’re done if you can show that $p_n^2+2p_np_{n+1}-p_{n+1}^2=(-1)^{n+1}$. Now just remember that by your induction hypothesis you have $p_{n-1}p_{n+1}-p_n^2=(-1)^2$, and notice that $p_n^2-p_{n-1}p_{n+1}=-(p_{n-1}p_{n+1}-p_n^2)$. – Brian M. Scott Jan 27 '15 at 22:36
• Found it this morning. A night sleep can do wonders, thanks for help =-) – Kamil Jan 28 '15 at 11:39
• @Kamil: It can indeed; you're welcome. – Brian M. Scott Jan 28 '15 at 17:31

You have shown that it is true for $n=1$. The next step is not to suppose it is true for $n>1$, but for $n=k$. Then you must show that it is true for $n=k+1$.

• ok, thanks for the heads up. – Kamil Jan 27 '15 at 22:26