# How to solve this recurrence $K(n)=2K(n-1)-K(n-2)+C$?

The recurrence is $K(n)=2K(n-1)-K(n-2)+C$ where $C$ is a constant. What I have tried is substituting $2K(n-1)$ as we do in fibonnacical recurrences. It didn't gave me a fruitful expression! Can someone help in solving it? Not a homework problem.

$$\begin{bmatrix} K(n+1) \\ K(n) \end{bmatrix}=A \begin{bmatrix} K(n) \\ K(n-1) \end{bmatrix}+ \begin{bmatrix} C \\ 0 \end{bmatrix}$$

where

$$A= \begin{bmatrix} 2 & -1 \\ 1 & 0 \end{bmatrix}.$$

Therefore,

$$\begin{bmatrix} K(n+1) \\ K(n) \end{bmatrix}=A^n \begin{bmatrix} K(1) \\ K(0) \end{bmatrix}+ \left(\sum_{k=1}^{n-1}A^k+I\right) \begin{bmatrix} C \\ 0 \end{bmatrix}$$

and

$$K(n)=nK(1)-(n-1)K(0)+\frac{1}{2}Cn(n-1)$$

by noticing that

$$A^k= \begin{bmatrix} k+1 & -k \\ k & k-1 \end{bmatrix}.$$

### The other answers are way too complicated for this particular problem.

They're useful in more general cases, but they're completely overkill here.

\begin{align*} K(n) &= 2 K(n - 1) - K(n - 2) + C \\ K(n) - K(n - 1) &= K(n - 1) - K(n - 2) + C \end{align*}

Just look at this equation for a few seconds.
It's literally telling you that the difference between successive elements increases by $C$ every step.
So... just go ahead and count how many times you add $C$ to the difference $K(1) - K(0)$:

$$K(n) = K(0) + \sum_{k=1}^{n} K(1) - K(0) + (k - 1) C$$

Notice you don't need any linear algebra, eigenvectors, or other higher-level math for this problem. It's just algebraic manipulation.

I'll leave the last step of simplifying the summation to you.

## Edit:

or I'll just do it for you myself, since you seem to think it leads to another recurrence...

\begin{align*} K(n) &= K(0) + n(K(1) - K(0)) + C\sum_{k=1}^{n} (k-1) \\ &= K(0) + n(K(1) - K(0)) + C \frac{n(n-1)}{2} \end{align*}

• indeed Beautiful ! – Shubham Sharma Jul 9 '15 at 11:09
• Thanks! I'll admit that it wasn't obvious to me -- at first I was trying to be "creative" by turning this into a continuous equation, via converting differences into derivatives and seeing if I knew the solution to the (delay-?)differential equation. But as soon as I subtracted $K(n-1)$ from both sides to turn the differences into derivatives, I saw there was a much easier way to solve this, hence this answer. :) – Mehrdad Jul 9 '15 at 11:12
• @MichaelGaluza: Dude, my solution is quadratic... – Mehrdad Jul 9 '15 at 15:42
• @ShubhamSharma: Michael is totally wrong, but do you really need me to do the last step for you? No, this shouldn't lead you to another recurrence. It just simplifies to $K(0) + n(K(1) - K(0)) - n + C\sum_{k=1}^{n} k$ and $\sum_{k=1}^{n} k$ is just $n(n+1)/2$. This is the right answer to your question. – Mehrdad Jul 9 '15 at 15:46
• @ShubhamSharma: I just realized, you might want to look up the phrase linear constant-coefficient difference equation. – Mehrdad Jul 9 '15 at 17:08

To keep things general, suppose $k_0=A$ and $k_1=B$. Then the next few terms are: $$k_2=2A-B+C\\ k_3=4A-3B+3C\\ k_4=6A-5B+6C\\ k_5=8A-7B+10C\\ k_6=10A-9B+15C$$

The pattern seems to be (for $n\ge2$) that 2 more $A$'s are added, 2 more $B$'s are subtracted, and $n-1$ more $C$'s are added, $$k_n=(2n-2)A-(2n-3)B+\frac{(n-1)(n)}{2}C$$

A proof by strong induction along with some messy algebra will give you your answer

More standard way. Rewrite your equation: $$K(n)-2K(n-1)+K(n-2)=C \tag{1}\label{1}$$ Solution of this is $K=K_0+K_{part}$, where $$K_0(n)-2K_0(n-1)+K_0(n-2)=0\tag{2}\label{2}$$ and $K_{part}$ is any solution of $\eqref{1}$.

Now we're finding solution of homogenuous equation $\eqref{2}$ in a form $K(n)=\mathrm{const}\cdot \lambda^n$ and get $$\lambda^{n}-2\lambda^{n-1}+\lambda^{n-2}=0\Longrightarrow \lambda^2-2\lambda+1=0;$$ $\lambda_1=\lambda_2=1$, and $$K_0(n)=A+Bn.\tag{3}\label{3}$$

$K_{part}$ we'll find in a form $K_{part}=\alpha n^2$ (polynom of degree $0$ and $1$ we used yet). Substitute it in $\eqref{1}$ and get $2\alpha=C$.

So, solution is $$K(n)=A+Bn+\frac{Cn^2}{2}.$$

If you prefer, we can take $K(0)=A$ and $K(1)=A+B+C/2$; hence, $$K(n)=K_0+(K_1-K_0)n+\frac{Cn(n-1)}{2}$$

• might be nice to explain how you just came up with the form $c \lambda^n$, because it looks pretty magical to someone who doesn't already know that's the right thing to do. – Mehrdad Jul 9 '15 at 10:02
• @Mehrdad, I can say just "it works". But, if you want perfect rigor, read whatever contains "recurrence relation". – Michael Galuza Jul 9 '15 at 11:35