3
$\begingroup$

Given that $F_n=F_{n-1}+F_{n-2}$, with initial conditions $F_1=1$ and $F_2=3$. Provide a formula, without solving for the recurrence, for $F_1+F_2+...+F_n$.

Any ideas how I should do this question without the use of the recurrence formula? I know that I can solve for a recurrence formula and using sum of the geometric progression, I am able to get an answer. However, how would you do that without solving for the recurrence?

This is what I have obtained so far:

$F_3=F_2+F_1\\F_4=F_3+F_2\\F_5=F_4+F_3\\...$

My sum is this:

$F_1+F_2=F_1+F_2\\F_1+F_2+F_3=2F_2+2F_1\\F_1+F_2+F_3+F_4=4F_2+3F_1\\F_1+F_2+F_3+F_4+F_5=7F_2+5F_1\\F_1+F_2+F_3+F_4+F_5+F_6=12F_2+8F_1$

I think I'm beginning to see a pattern here: That is, the sum of the 2 coefficients in the previous term of $F_1$ and $F_2$ is the current coefficient of $F_2$, and that the current coefficient of $F_1$ is the sum of the previous 2 coefficients of $F_1$.

However, how am I suppose to find a formula linking $F_1+F_2+F_3+...+F_n$?

There is an additional information in the question, but I'm not sure if the hint is useful.

The hint is: Consider $F_1^2+F_2^2+F_3^2+...+F_n^2=F_nF_{n+1}-2$

Is there anything I am missing out?

$\endgroup$
  • $\begingroup$ Also, combine this question with this one. $\endgroup$ – Dietrich Burde Apr 25 '17 at 12:43
  • $\begingroup$ Thanks I will look into it! The initial conditions changes, so I guess there will be some changes to the formulas as well $\endgroup$ – Icycarus Apr 25 '17 at 12:46
  • $\begingroup$ Then it also would change the formula from the above hint, $F_1^2+F_2^2+F_3^2+...+F_n^2=F_nF_{n+1}-2$. $\endgroup$ – Dietrich Burde Apr 25 '17 at 13:05
  • $\begingroup$ See math.stackexchange.com/questions/1042364/… $\endgroup$ – lhf Apr 25 '17 at 13:35
  • $\begingroup$ The conjecture that follows from your observations is $F_1+F_2+F_3+\cdots+F_n = (f_{n+1}-1)F_2+ f_n F_1$ where $f_n$ is the $n$-th Fibonacci number. $\endgroup$ – lhf Apr 25 '17 at 14:03
4
$\begingroup$

The recurrence $F_{n+2}=F_{n+1}+F_n$ implies that the characteristic polynomial of the given sequence is $x^2-x-1$, hence $$ F_n = A \sigma^n + B\bar{\sigma}^n \tag{1}$$ with $A,B$ being constants depending on the initial conditions and $\sigma=\frac{1+\sqrt{5}}{2},\bar{\sigma}=\frac{1-\sqrt{5}}{2}$ being the roots of the characteristic polynomial. In particular, even without computing $A$ and $B$ we have

$$ F_1+F_2+\ldots+F_N = A \sum_{n=1}^{N}\sigma^n+B\sum_{n=1}^{N}\bar{\sigma}^n = A\frac{\sigma^{N+1}-1}{\sigma-1}+B\frac{\bar{\sigma}^{N+1}-1}{\bar{\sigma}-1}\tag{2}$$ and the LHS of $(2)$ can be expressed as $C F_{N+1}+ D F_{N+2}+E$ for some constants $C,D,E$ that we may compute by interpolation. Since $\{F_1,F_2,F_3,F_4,F_5\}=\{1,3,4,7,11\}$ we have $$\left\{\begin{array}{rcl} 3C+4D+E &=& 1 \\ 4C+7D+E &=& 4 \\ 7C+11D+E&=& 8\end{array}\right.\tag{3} $$ so $\{C,D,E\}=\left\{ 0,1,-3 \right\}$ and we are done: $$ F_1+F_2+\ldots+F_N = \color{red}{F_{N+2}-3}.\tag{4}$$ On the other hand, once $(4)$ is established as a conjecture it is straightforward to prove by induction.

$\endgroup$
  • 1
    $\begingroup$ Oh!!! I see it now! Thank you very much!! $\endgroup$ – Icycarus Apr 25 '17 at 13:37
  • $\begingroup$ @Icycarus: you're welcome. $\endgroup$ – Jack D'Aurizio Apr 25 '17 at 13:37
1
$\begingroup$

Every sequence satisfying the Fibonacci recurrence can be written as $$ F_n = f_{n-2} F_1 + f_{n-1} F_2 $$ where $f_n$ is the $n$-th Fibonacci number. This follows immediately by induction.

For your sequence, we have $$ F_n = f_{n-2} +3 f_{n-1} = f_{n-2} + f_{n-1} + 2f_{n-1} = f_n + f_{n-1} + f_{n-1} = f_{n+1} + f_{n-1} =f_{n+2}-f_{n-2} $$

(Incidentally, your $F_n$ is the $n$-th Lucas number.)

Therefore, $$ \begin{align} \sum_{i=1}^n F_i &= F_1 + \sum_{i=2}^n f_{i+2} - \sum_{i=2}^n f_{i-2} \\&= F_1 +f_{n-1}+f_{n}+f_{n+1}+f_{n+2}-f_0-f_1-f_2-f_3 \\&= f_{n-1}+f_{n}+f_{n+1}+f_{n+2}-3 \\&= f_{n+1}+f_{n+3}-3 \\&= F_{n+2}-3 \end{align} $$

If you happened to know that $\sum_{i=0}^{n} f_{i}=f_{n+2}-1$, then $$ \begin{align} \sum_{i=1}^n F_i &= F_1 + \sum_{i=2}^n f_{i-2} F_1 + \sum_{i=2}^n f_{i-1} F_2 \\&= F_1 + (f_n-1)F_1 + (f_{n+1}-1)F_2 \\&= f_nF_1 + f_{n+1}F_2 - F_2 \\&= F_{n+2}-3 \end{align} $$

$\endgroup$
1
$\begingroup$

We can use finite differences.

Let $\phi(n) = \sum_{i=1}^nF_i$

$\Delta \phi(n) = \sum_{i=1}^{n+1}F_i - \sum_{i=1}^nF_i = F_{n+1}$

We know $\Delta F_n = F_{n+1} - F_n = F_{n-1}$,

So $\Delta \phi(n) = F_{n+1} = \Delta F_{n+2} \implies \sum_{i=1}^nF_i = F_{n+2} + C$ where C is a constant of summation.

For $n = 1$, we get $F_1 = F_3 + C \implies C = F_1 - F_3 = -F_2$

So $\sum_{i=1}^nF_i = F_{n+2} - F_2$

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