3
$\begingroup$

Find sum $\sum _{k=0}^nF_kF_{n-k}$

My try

Let $$ a_n = \sum _{k=0}^nF_kF_{n-k} // \cdot x^n \\ a_n x^n = \sum _{k=0}^nF_k x^k F_{n-k} x^{n-k} // \sum_n \\ A(x) = (F(x))^2 + \cdots + (F(x))^2 = n\cdot (F(x))^2$$

I have some doubts:

  • I am not sure that summing $F_k x^k$ by $n$ gives $F(x)$ (generating functions for $f_n$ sequence)
  • If it is true, how can it be finished? There is weird situation. I know that $a_n$ is a element from $\sum _{k \ge 0} F_k \cdot \sum _{k \ge 0} F_k$ multiplied by $n$ but it is not obvious for me how it can be extracted from there.
$\endgroup$
  • $\begingroup$ The MathJax is not clear. What does $// \cdot$ mean? $\endgroup$ – Peter Foreman Aug 18 at 14:23
  • $\begingroup$ multiplying both sides by $\endgroup$ – Tester1998 Aug 18 at 14:24
  • $\begingroup$ Generally $//$ means that I am do something for both sides $\endgroup$ – Tester1998 Aug 18 at 14:24
  • 1
    $\begingroup$ If that's the case, what does $//\sum_{n}$ mean? That most certainly is abuse of notation. $\endgroup$ – Don Thousand Aug 18 at 14:31
  • $\begingroup$ Consider $F(x)^2.$ $\endgroup$ – Lord Shark the Unknown Aug 18 at 14:52
5
$\begingroup$

Hint: Convolution of sequences corresponds to the multiplication of their generating functions. The generating function of Fibonacci sequence is $$F(z) = (\frac{1}{\sqrt5})(\frac{1}{1-\phi z} - \frac{1}{1-\hat{\phi} z})$$

Thus, we need the coefficient of $z^n$ in $F^2(z)$

$F^2(z) = \frac{1}{5}(\frac{1}{(1-\phi z)^2} + \frac{1}{(1-\hat{\phi} z)^2}-\frac{2}{(1-\phi z)(1-\hat{\phi}z)})$

$F^2(z) =\frac{1}{5}(\Sigma_{n\ge 0}(n+1)\phi^n z^n - 2\Sigma_{n\ge 0}f_{n+1} z^n+\Sigma_{n\ge 0}(n+1)\hat{\phi}^n z^n)$

$F^2(z) =\frac{1}{5}(\Sigma_{n\ge 0}(n+1)(2f_{n+1} - f_{n})z^n - 2\Sigma_{n\ge 0}f_{n+1}z^n)$

$\therefore \sum _{k=0}^nf_kf_{n-k} = \frac{2nf_{n+1} - (n+1)f_{n}}{5}$

$\endgroup$
1
$\begingroup$

I guessed the formula, then prove it by induction.
Let $s_n = \sum_0^n F_k F_{n-k}$

From identity: $F_m F_n = F_m F_{n+1} + F_{m-1} F_n$

$s_n = (n-1) F_{n-1} - s_{n-2}$
$s_n = (n-1) F_{n-1} - (n-3) F_{n-3} + (n-5) F_{n-5} - \cdots$

Simplify the sum, so that $s_n = a F_{n} + b F_{n-1}$, and build a table:

$$\begin{matrix} n & s_n & a & b \cr 2 & 1 & 1/5 & 4/5 \cr 3 & 2 & 2/5 & 6/5 \cr 4 & 5 & 3/5 & 8/5 \cr 5 & 10 & 4/5 & 10/5 \cr 6 & 20 & 5/5 & 12/5 \end{matrix}$$

Guessed formula for $s_n = \frac{(n-1)F_n + 2 n F_{n-1}}{5}$

The prove is in pairs, check n=1,2; assumed true for n=k; check n=k+2:
For n=1, $\frac{(1-1)(1) + (2)(1)(0)}{5} = 0$
For n=2, $\frac{(2-1)(1) + (2)(2)(1)}{5} = 1 = F_1^2$

For n=k+2, use recurrence formula to build $s_{k+2}$:

$$(k+1)F_{k+1} - \frac{(k-1)F_k + 2 k F_{k-1}}{5} = \frac{((k+2)-1)F_{k+2} + 2 (k+2) F_{(k+2)-1}}{5}$$

QED

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