What does it mean to solve recurrence relation?
$$f(n)=3f(n-1)-f(n-2)-3f(n-3)+2f(n-4)-4$$$$f(0)=0,f(1)=1,f(2)=2,f(3)=3$$Given some recurrence relation with these starting conditions.
What does it mean to solve it? I don't need a solution for the exersice, just a clarification on the meaning of "solving it"?
-Edit:
After examining the answers, I get this solution:
$$f(n)-3f(n-1)+f(n-2)+3f(n-3)-2f(n-4)+4=0$$
In order to a general solution I "discarded" the '4' and wrote it like this, using characteristic polynomial: $$x^{4}-3x^{3}+x^{2}+3x-2=0$$
The solutions for this equations are: 2,1,-1
Then I wrote it like this: $a_{n}=a_{1}2^{n}+a_{2}1^{n}+a_{3}(-1)^{n}-4$
Is that the right direction for solving this equation? afterwards I think I suppose to solve 4 equations using the 4 starting conditions at the beginning.
$\endgroup$ 31 Answer
$\begingroup$Solving the recurrence means expressing $f(n)$ in terms of $n$ and no other instance of $f$. You give an explicit expression of $f$ instead of an implicit one.
E.g.
$$f(n)=f(n-1)+1,\\f(0)=0$$ is a recurrence which is solved by
$$f(n)=n.$$
Likewise, solving the quadratic equation
$$x^2+2x+1=0$$ is making $x$ explicit,
$$x=-1.$$
$\endgroup$
