Find a conjecture for $F_1+F_2+...+F_n$ 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? 
 A: 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.
A: 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}
$$
A: 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$
