# $f(n) = 2f(n-1) -f(n-2) + 1$ find closed form by repeated substitution

$$f(0)=a$$ $$f(1)=b$$

$$f(n) = 2f(n-1) -f(n-2) + 1$$ How can I begin repeated substitution with this? I'm confused because there are two $f$ terms not sure how to sub for both of them.

• $f(n) - f(n-1) = g(n)$, then $g(n) = g(n-1) + 1$. – Yimin Mar 1 '16 at 19:53

After some computations $$f(2) = 2f(1)-f(0)+1 = 2b-a+1,$$ $$f(3) = 2f(2)-f(1)+1 = 4b-2a+2-b+1 = 3b-2a+3,$$ $$f(4) = 2f(3)-f(2)+1 = 6b-4a+6-2b+a-1+1 = 4b-3a+6,$$ you can conjecture that $$f(n) = nb-(n-1)a+ \frac{n(n-1)}{2}$$ and prove this by induction.

I like to express recursions of this type by matrix-expressions, such that with a initial vector $$[1,a,b]$$ we get by the transfer matrix $$M$$ the vector $$[1,b,c]$$ where $$b$$ and $$c$$ are defined by one step of the recursion.
For your problem $$M = \begin{bmatrix} 1&0&1 \\\ 0&0&-1 \\\ 0&1&2 \end{bmatrix}$$ and then $$[1,a_1,a_2] \cdot M^h = [1,a_h,a_{h+1}] \tag 0$$ where $$h$$ is then the iteration-"height".

Often diagonalization of the transfermatrix $$M$$ allow then the direct expression of the matrixpower $$M^h$$ in a formula with $$h$$ kept indeterminate.

In your case I don't find a diagonalization for $$M$$ but a "similarity"-transformation (or "Schur-decomposition") of $$M$$ into $$D$$ such that with the orthogonal ("rotation"-) matrix $$T$$ and a triangular matrix $$D$$ $$M = T^\tau \cdot D \cdot T \tag 1$$ such that $$M^h = T^\tau \cdot D^h \cdot T \tag 2$$
Here the superpostfix $$\tau$$ at matrixname $$T$$ means "transpose" but, because $$T$$ is constructed to be orthogonal, means also the inverse and thus we have indeed a "similarity" transformation.

Here $$D$$ has the identity-diagonal and $$D^h = \exp(h \cdot \log(D))$$ can be given in exact polynomial terms of $$h$$.
Let's denote $$q = \sqrt {0.5}$$ then I found that a valid solution for $$T$$ is $$T= \begin{bmatrix} 0&0&1 \\\ q&-q&0 \\\ q&q&0 \end{bmatrix} \tag 3$$ then
$$D= T^\tau \cdot M \cdot T= \begin{bmatrix} 1&0&0 \\\ 2&1&0 \\\ q&q&1 \end{bmatrix} \tag 4$$ The matrix-logarithm of $$D$$ is then $$\Lambda= \log(D)= \begin{bmatrix} 0&0&0 \\\ 2&0&0 \\\ 0&q&0 \end{bmatrix} \tag 5$$ and $$D^h$$ has then the simple form $$D^h = \exp(h \cdot \Lambda) = \begin{bmatrix} 1&0&0 \\\ 2h&1&0 \\\ q \cdot h^2&q \cdot h&1 \end{bmatrix} \tag 6$$ and $$M^h$$ is then $$M^h = T \cdot D^h \cdot T^\tau = \begin{bmatrix} 1& \frac12 h(h-1)& \frac 12 h(h+1) \\\ 0&1-h&-h \\\ 0& h&h+1 \end{bmatrix} \tag 7$$ and thus using eq $$(0)$$ $$[1, a_1, a_2] \cdot M^h = [1, a_h, a_{h+1}] \\\ a_{h+1}= \left([1,a_1,a_2] \cdot M^h\right) $$ we get $$a_{h+1} = \frac12h(h+1) -h\cdot a_1 + (h+1) a_2 \tag 8$$

Remarks:

• the equation (5) can exactly be determined by the mercatorseries for $$(D-I)$$ because $$D-I$$ is nilpotent and the series collapses to a finite sum.
• the equation (6) can exactly be determined by the common exponential-series on $$h\cdot \Lambda$$ because $$h\cdot \Lambda$$ is nilpotent and the exponential series collapses to a finite sum.
• In light of some other questions of the same type but where the triangular matrix D has entries $$\ne 1$$ in the diagonal it might be even better, more general and thus the "canonical" solution, to use the Jordan-decomposition $$M=S \cdot J \cdot S^{-1}$$ instead where the matrix J has an even simpler form than D and the matrix-log and -exponential can as easy be computed as with the diagonalization in the diagonalizable cases. Unfortunately, the Jordan-decomposition is tedious even with $$3\times3$$-matrices (but can for instance be called from Wolfram-Alpha) so I proposed the triangular decomposition-version here.

Since $$f(n)-2f(n-1)+f(n-2)=1$$ if we let $$g(n)=f(n)-\frac{n^2}2$$ we get $$g(n)-2g(n-1)+g(n-2)=0$$ the solution to which is $$g(n)=cn+d$$, since the characteristic polynomial is $$(x-1)^2$$. Thus, because $$f(0)=a$$ and $$f(1)=b$$, $$f(n)=\frac{n^2-n}2+(b-a)n+a$$

A standard way to do this is through generating function.

The generating function of $$f(n)$$ is $$g(z)=\sum_{n \ge 0} f(n)z^n$$ Multiply both sides of the recursion by $$z^{n}$$ gives $$z^{n}f(n+2) = 2 z^{n} f(n+1) - z^{n}f(n) + z^n$$ Sum over $$n \ge 0$$ and we get $$\frac{-a-b z+g(z)}{z^2}=\frac{2 (g(z)-a)}{z}-g(z)+\frac{1}{1-z}$$ Solving this gives $$g(z)=\frac{-2 a z^2+3 a z-a+b z^2-b z-z^2}{(z-1)^3}$$ Now you can get the coefficient of $$g(z)$$ by applying a binomial expansion to $$(z-1)^{-3}$$.

• Thank you again, I deleted my question there since you answer it fully. – Aqua Dec 16 '19 at 19:29