Like in the title the following equation:

  1. $F(n)=F(n-1)+F(n-2)+f(n)$, with $F(0)=0, F(1)=1$
  2. $f(n)=f(n-1)+f(n-2)$, with $f(0)=0, f(1)=1$

I don't know how to solve this. The $f(n)$ is basically just $F(n)$, but then I have $$F(n)=F(n-1)+F(n-2)+F(n) \Rightarrow F(n-1)+F(n-2)=0$$ and I cannot go anywhere from this.

  • 1
    $\begingroup$ Use a spreadsheet and run the numbers. Seems to be that F(n) ≈ 0.72 * n * fib(n). Now figure out why. $\endgroup$
    – gnasher729
    Dec 8, 2018 at 15:38
  • $\begingroup$ Can you credit the original source of the problem? $\endgroup$
    – John L.
    Dec 9, 2018 at 3:41
  • $\begingroup$ @TomZych Your comment comes across as unnecessarily hostile. Also, you're wrong. If gnasher had thought that the recurrence was $F(n)=F(n-1)+F(n-2)+F(n)$, then the $F(n)$ terms cancel and we get $F(n-1)=-F(n-2)$, so the sequence would be $0, 1, -1, 1, -1, \dots$. Conversely, if they thought they were trying to solve $f(n)=f(n-1)+f(n-2)$, then the answer would be just $\mathrm{fib}(n)$, not the answer given. $\endgroup$ Dec 9, 2018 at 16:51
  • $\begingroup$ @TomZych I don't think you can expect people to guess that the rule is "If it's gnasher, I'll use their name so if I just say 'you' it means Mat" rather than "If it's Mat, I'll use their name so if I just say 'you' it means gnasher." But, anyway, once you've pointed out that somebody has misread something, there's no need to tell them to read it again. It should be obvious to anyone who is told that they have misread something that they should read it again, and read it more carefully. Explicitly telling them seems patronizing, even if it's not intended to be. $\endgroup$ Dec 9, 2018 at 19:58
  • $\begingroup$ Suggested to use Tex formatting for mathematical formulae. $\endgroup$
    – hola
    Nov 23, 2019 at 10:57

1 Answer 1


$f(n)$ is the well-known Fibonacci sequence.

Let $\alpha=\frac{1+\sqrt5}2$ be the golden ratio and $\phi=\frac{1-\sqrt5}2$. It is shown here that $$f(n)=(\alpha^n-\phi^{n})/\sqrt5$$

Gnasher729 conjectured that $F(n) \approx 0.72 * n * f(n)$. Following that clue, we can find the following identity holds for all cases we tested by trial and error. $$F(n)= nf(n) - (n-2)f(n-2) + (n-4)f(n-4) - (n-6)f(n-6) + \cdots$$ where the sequence of summands goes on as long as the summand makes sense.

How to prove that long formula? We can observe it implies for $n\ge2$, $$ F(n) = nf(n) - F(n-2).$$

Let us prove that simple recurrence relation of $F(n)$ by induction on $n$.

The base cases when $n=2$ and when $n=3$ is easy since f(2)=1, f(3)=2, F(2)=1+0+1=2 and F(3)=2+1+2=5.

Suppose it is true for $n\le k$, where $k\ge3$. $$\begin{aligned} F(k+1) =& F(k) + F(k-1) + f(k+1)\\ =& (kf(k) - F(k-2)) + ((k-1)f(k-1) - F(k-3)) + f(k+1)\\ =& k(f(k)+f(k-1))-f(k-1) - (F(k-2)+F(k-3)) + f(k+1)\\ =& kf(k+1)-f(k-1) - (F(k-1)-f(k-1)) + f(k+1)\\ =& (k+1)f(k+1)- F(k-1)\\ \end{aligned}$$

Now that we have proved that simple recurrence relation of $F(n)$, it is immediate to prove that long formula, which can also be stated succinctly as

$$F(n)=\sum_{0\le i\lt n, i\text{ even}}(-1)^{i/2}f(n-i)$$

Interested readers may enjoy the following exercises, roughly in the order of increasing difficulty.

Exercise 1. Given the above formulas for $f(n)$ and $F(n)$, show that $F(n)=\Theta(n\alpha^n)$.

Exercise 2. Given the above formulas for $f(n)$ and $F(n)$, show that $$\lim_{n\to\infty}\frac{F(n)}{n\alpha^n}= \frac1{1+\alpha^{-2}}\approx 0.7236$$

Exercise 3. Find a close formula for $F(n)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.