-1

How can I solve the recurrence relation $f(n) = f(n-1) - f(n-2) + n$, given $f(1) = 1$ and $f(2) = 1$?

I know how to solve the characteristic equation however I don't know how to deal with the n term. Any help?

I know this can be solved generally with characteristic equations and polynomials I just can't find it.

jujumumu
  • 101
  • So, the characteristic equation lets you know about the general solution. You need to find the particular solution for what else there is, in this case the $+n$. That is a polynomial, so try to see if a polynomial will fit. – JMoravitz Nov 15 '22 at 02:02

1 Answers1

1

You just solve for the original equation ignoring the $n$, and add a linear term of $n$ at last. Another way of understanding this is to reduce the polynomial to zero by combining consecutive recurrences. $$f(n+1)-f(n)=f(n)-f(n-1)-(f(n-1)-f(n-2))+1$$ $$f(n+2)-f(n+1)-(f(n+1)-f(n))=f(n+1)-f(n)-(f(n)-f(n-1))-(f(n)-f(n-1)-(f(n-1)-f(n-2)))$$

In theory, you could find $f(3),f(4)$ and solve for this instead.

However notice that the original solutions of the quadratic equation is also the solutions of this four degree equation, with two additional root of $x=1$. This is always the case because of the way we construct the new recurrence. In your specific example,

$$x^4-x^3-(x^3-x^2) = x^3-x^2-(x^2-x)-(x^2-x-(x-1))$$

$$(x-1)(x^3-x^2)=(x-1)(x^2-x)-(x-1)(x-1)$$

$$(x-1)^2x^2=(x-1)^2x-(x-1)^2$$

Notice that the original characteristic equation is

$$x^2=x-1$$

And the new equation is exactly the same except the additional $(x-1)^2$ roots. This implies that you simply add a linear term ($Cn+D$) at last and have the general solution

$$A{x_1}^n+B{x_2}^n+Cn+D$$

In general, the original characteristic equation is always a factor of the new equation and you get some additional roots of $x=1$ in the end. You would deal with it identical with how you would deal with multiple repeated roots of $1$.

cr001
  • 12,598