7
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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*}

$\endgroup$
  • $\begingroup$ indeed Beautiful ! $\endgroup$ – Shubham Sharma Jul 9 '15 at 11:09
  • 1
    $\begingroup$ 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. :) $\endgroup$ – Mehrdad Jul 9 '15 at 11:12
  • 1
    $\begingroup$ @MichaelGaluza: Dude, my solution is quadratic... $\endgroup$ – Mehrdad Jul 9 '15 at 15:42
  • 1
    $\begingroup$ @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. $\endgroup$ – Mehrdad Jul 9 '15 at 15:46
  • 1
    $\begingroup$ @ShubhamSharma: I just realized, you might want to look up the phrase linear constant-coefficient difference equation. $\endgroup$ – Mehrdad Jul 9 '15 at 17:08
6
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mehrdad Jul 9 '15 at 10:02
  • $\begingroup$ @Mehrdad, I can say just "it works". But, if you want perfect rigor, read whatever contains "recurrence relation". $\endgroup$ – Michael Galuza Jul 9 '15 at 11:35

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.