1
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ $f(3)$ is redundant, since it can be calculated from $f(1), f(2)$. Lookup linear homogeneous recurrences. $\endgroup$ – dxiv Jan 15 '17 at 6:39
  • 1
    $\begingroup$ You can rewrite as f(x+1) = f(x) - f(x-1) or shifting, f(x) = f(x-1) - f(x-2). Now you can try out a few terms quickly: 4, 3, -1, -4, -3, 1, 4, ... It's cyclic. You should be able to take it from there. $\endgroup$ – 1110101001 Jan 15 '17 at 6:39
11
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ To add, once you compute the first six or so terms you can see a pattern emerge. $\endgroup$ – 1110101001 Jan 15 '17 at 6:41
  • $\begingroup$ Ya you are right $\endgroup$ – Gyanshu Jan 15 '17 at 6:45
2
$\begingroup$

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

$\endgroup$

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.