Recurrence Relation: $f(x)=f(x-1)+f(x+1)$ While learning about functions (mainly basic transformations, i.e. reflections, stretches, etc.), I stumbled upon this question:
$$f(x)=f(x-1)+f(x+1), \\\text{what is the value of}\ f(1867)?$$
where $f(1)=1, f(2)=4, \ \text{and}\  f(3)=3$.
I solved this with Python, finding that $f(1867)=1$. However, after having spent many hours trying to solve it mathematically and research recurrence relations, I still could not do it. How would you solve it mathematically, using knowledge of only basic properties of functions? (I'm assuming that this is possible since the question is a part of a course). 
 A: Replace $x+1$ with $y\space$ i.e. replacing $x$ with $y-1$
$$f(y-1)=f(y-2)+f(y)$$
$$\implies f(y) = f(y-1)-f(y-2)$$
You can compute all elements easily now.
Then we can see a pattern
$$1,\space4,\space3,\space-1,\space-4,\space-3,\space 1,\space4,\space3,\space-1,\space-4,\space-3$$
with a period of $6$. You can do the last step yourself.
A: Note that $$f(x)=f(x-1)+f(x+1)$$ $$f(x-1)=f(x)+f(x-2)$$
Adding these two, we get $$f(x+1)=-f(x-2) \implies \boxed{f(x)=-f(x-3)}$$
Iterate this to get $$f(x)=-f(x-3)=f(x-6)= \ldots = (-1)^k f(x-3k)$$
$$\implies \boxed{f(x)=(-1)^k f(x-3k)}$$
Now, $1867=3 \times 622 + 1$.
So, we have $$f(1867)=(-1)^{622} f(1867-3\times 622)=f(1)=1$$
Hope this helps you.
Addendum: In general, we can conclude that $$f(3k+1)=(-1)^{3k+1} f(1)=(-1)^k$$
$$f(3k+2)=(-1)^{3k+2} f(2)=(-1)^{k}4$$
$$f(3k+3)=(-1)^{3k+3} f(3)=(-1)^{k+1}3$$
A: $$ f(x+2)+f(x)=f(x+1) $$
$$ f(x+3)+f(x+1)=f(x+2) $$
Add both the equations to get
$$ f(x+3)+f(x)=0$$ for every real $x$.
You have also $f(x+6)+f(x+3)=0$ for every real $x$, and therefore $$f(x)=f(x+6)$$ for every real $x$.
Hence, the period of the function is $6$. Now, $$f(1867) = f(1866+1) = f(6\times311 + 1) = f(1) = 1$$
