0

Consider the following system of linear recurrence relations.

$$\begin{aligned} p_n &= a \cdot p_{n-1} - c_{n-1}\\ c_{n-1} &= p_{n-1} - b \cdot p_{n-2} + c_{n-2}\end{aligned}$$

with $p_0 = 1$ and $c_1 = 1$.

I've tried to represent $p_n$ as a finite linear combination of $p_{k}, k < n$, but this doesn't work for me. Maybe there is any chance to represent the final solution?

Any ideas?

Rodrigo de Azevedo
  • 1
openspace
  • 6,470
  • @RodrigodeAzevedo I thought about it, but there are a different number of variables in these two equations. – openspace Apr 04 '21 at 02:10

2 Answers2

4

Note that \begin{align} p_n-p_{n-1} &= (ap_{n-1}-c_{n-1})-(ap_{n-2}-c_{n-2})\\ &=a(p_{n-1}-p_{n-2})-(p_{n-1}-bp_{n-2})\\ \implies p_n&=ap_{n-1}+(b-a)p_{n-2} \end{align} Now use the standard way to solve recursions of this form (by solving the corresponding quadratic equation).

Martund
  • 14,706
  • 2
  • 13
  • 30
  • we also get such a recurrence for $c_i$ from Cayley-Hamilton for the matrix in the other answer. Same coefficients as for $p_i$ – Will Jagy Apr 04 '21 at 03:08
  • @WillJagy, That's right, but using such a concept for solving a recursion as simple as this, is too much. – Martund Apr 04 '21 at 06:08
1

Hint:

It's helpful to have the indices line up, so let's rewrite this as

$$ \begin{aligned} p_n &= a p_{n-1} - c_{n-1} \\ c_n &= p_n - b p_{n-1} + c_{n-1} \end{aligned} $$

Of course, we can use the known definition of $p_n$ to get

$$ \begin{aligned} p_n &= a p_{n-1} - c_{n-1} \\ c_n &= (a-b) p_{n-1} \end{aligned} $$

It's helpful to keep track of all this in a matrix, as such:

$$ \begin{pmatrix} p_{n} \\ c_{n} \end{pmatrix} = \begin{pmatrix} a & -1 \\ a-b & 0 \end{pmatrix} \begin{pmatrix} p_{n-1} \\ c_{n-1} \end{pmatrix} $$

Do you see where to go from here? You'll want to consider powers of this $2 \times 2$ matrix applied to your initial condition $\begin{pmatrix} p_1 \\ c_1 \end{pmatrix}$. Note also that you were given $p_0$, so you'll need to compute $p_1$ by hand to get going.

I hope this helps ^_^

HallaSurvivor
  • 38,115
  • 4
  • 46
  • 87
  • and Cayley-Hamilton for your square matrix gives separate recurrences for $c_n$ and for $p_n.$ See the other answer for $p_n$ – Will Jagy Apr 04 '21 at 03:09