how to calculate a modified fibonacci via matrix exponentiation

Question

If I modify the fibonacci recurrence to be the following way:

f(0) = 1

f(1) = 1

f(N) = f(N - 1) + f(N - 2) + 1

Is it possible to represent this recurrence in a matrix equation similar to the one below? If so, how would I do write that?

Answer 1

While Daniel Fischer's approach in comments is the straighter approach, we can also express $\{f_n\}$ via matrix multiplication as

$$ \begin{pmatrix} f_{n+2}\\ f_{n+1} \\ 1\end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} f_{n+1}\\ f_{n} \\ 1\end{pmatrix}\tag{1} . $$

So the only change needed is to use a 3-by-3 matrix to generate this modified Fibonacci sequence.

---

To draw a direct linkage to Daniel's remark, note that $g_n:=f_n+1$ amounts to the matrix transformation

$$ \begin{pmatrix} g_{n+2}\\ g_{n+1}\\1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} f_{n+2}\\ f_{n+1} \\ 1\end{pmatrix}.\tag{2} $$

Then applying eq. $(1)$ to eq. $(2)$ gives \begin{align} \begin{pmatrix} g_{n+2}\\ g_{n+1}\\1 \end{pmatrix} &= \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} f_{n+1}\\ f_{n}\\1 \end{pmatrix}\\ &= \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}^{-1} \begin{pmatrix} g_{n+1}\\ g_{n}\\1 \end{pmatrix}\\ &= \begin{pmatrix} 1 & 1 & 2 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & -1 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} f_{n+1}\\ f_{n}\\1 \end{pmatrix}\\ &= \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} g_{n+1}\\ g_{n}\\1 \end{pmatrix} \end{align}

So we have $\begin{pmatrix} g_{n+2}\\ g_{n+1}\end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} g_{n+1}\\ g_{n}\end{pmatrix} $ i.e. $\{g_n\}$ is generated by the same matrix multiplication as the usual Fibonacci sequence.