Twin series

Number Theory Level 4

The Fibonacci sequence $(F_n)$ is defined as $F_0 = 1, F_1 = 1, F_n = F_{n-1} + F_{n-2}\ \text{for}\ n \geq 2.$

A Brilliant user asks his fellow math lovers to determine whether the equation $\sum_{k = 0}^n \left(\begin{array}{c} n \\ k \end{array}\right) F_k = F_{2n}\ \ \ \ \ \ (\star)$ is true for all integers $n \geq 0$ .

However, this Brilliant user is confused and accidentally defines the Fibonacci sequence alternatively as $F'_0 = 1, F'_1 = 2, F'_n = F'_{n-1} + F'_{n-2}\ \text{for}\ n \geq 2.$

Is equation $(\star)$ true for the original definition of $F_n$ , or for the new definition $F'_n$ ?

For both sequences For neither of these sequences Only for the original sequence,

F_n

Only for the alternative sequence,

F'_n

1 solution

Arjen Vreugdenhil
Jan 31, 2017

In general, if $F_n = F_{n-1} + F_{n-2}$ , then $F_n$ can be written as $F_n = A_1\phi_1^n + A_2\phi_2^n,$ where $\phi_{1,2}$ are solutions of $\phi^2 = \phi+1$ .

Thus $F_{2n} = A_1\phi_1^{2n} + A_2\phi_2^{2n} = A_1(\phi_1^2)^n + A_2(\phi_2^2)^n = A_1(\phi_1 + 1)^n + A_2(\phi_2 + 1)^n \\ = A_1\sum_{k=0}^n \left(\begin{array}{c} n \\ k\end{array}\right) \phi_1^k + A_2\sum_{k=0}^n \left(\begin{array}{c} n \\ k\end{array}\right) \phi_2^k = \sum_{k=0}^n \left(\begin{array}{c} n \\ k\end{array}\right) (A_1\phi_1^k + A_2\phi_2^k) = \sum_{k=0}^n \left(\begin{array}{c} n \\ k\end{array}\right) F_k.$

Thus the equation is true for any sequence defined be recursion $F_n = F_{n-1} + F_{n-2}$ , independent on the value of $F_0$ or $F_1$ ; specifically it is true for $\boxed{\text{both}}$ .

Twin series

1 solution

0 pending reports