1
$\begingroup$

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.

Improve this question
$\endgroup$
  • 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 '18 at 15:38
  • $\begingroup$ Can you credit the original source of the problem? $\endgroup$ – John L. Dec 9 '18 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$ – David Richerby Dec 9 '18 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$ – David Richerby Dec 9 '18 at 19:58
  • $\begingroup$ Suggested to use Tex formatting for mathematical formulae. $\endgroup$ – hola Nov 23 '19 at 10:57
1
$\begingroup$

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

Improve this answer
$\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.