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


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?

  • $\begingroup$ 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). $\endgroup$ – Kamil Jan 27 '15 at 22:24
  • $\begingroup$ @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)$. $\endgroup$ – Brian M. Scott Jan 27 '15 at 22:36
  • $\begingroup$ Found it this morning. A night sleep can do wonders, thanks for help =-) $\endgroup$ – Kamil Jan 28 '15 at 11:39
  • $\begingroup$ @Kamil: It can indeed; you're welcome. $\endgroup$ – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.