0
$\begingroup$

$$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.

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

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.

| cite | improve this answer | |
$\endgroup$
2
+25
$\begingroup$

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) [3] $$ 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.
| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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 $$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you again, I deleted my question there since you answer it fully. $\endgroup$ – Aqua Dec 16 '19 at 19:29

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.