If $a_{n+1} = a_n+a_{n-1}$,
$a_n = a_{n+1}-a_{n-1}$.
Therefore
$\begin{align}
\sum_{k=0}^n a_k
&=a_0+\sum_{k=1}^n a_k\\
&=a_0+\sum_{k=1}^n (a_{k+1}-a_{k-1})\\
&=a_0+\sum_{k=1}^n a_{k+1}- \sum_{k=1}^na_{k-1}\\
&=a_0+\sum_{k=2}^{n+1} a_{k}- \sum_{k=0}^{n-1}a_{k}\\
&=a_0+(\sum_{k=2}^{n-1} a_{k}+a_n+a_{n+1})- (a_0+a_1+\sum_{k=2}^{n-1}a_{k})\\
&=a_0+(a_n+a_{n+1})- (a_0+a_1)\\
&=a_{n+2}- a_1\\
\end{align}
$
This is your statement about the sum,
but it is true for any sequence
that satisfies the Fibonacci
recurrence, not just
the standard one.
So,
you only ("only"!)
have to compute $a_{n+2}$.
As shown in the standard way
by Adi Dani,
the generating function for
the $a_n$ is
$F(x)=\dfrac{1+5x}{1-x-x^2}$.
You then have to write
$1-x-x^2
=(1-ax)(1-bx)$
in the usual standard way
(all this is the traditional way
to get Binet's formula),
get $a$ and $b$,
find $c$ and $d$ such that
$\dfrac1{(1-ax)(1-bx)}
=\dfrac{c}{1-ax}+\dfrac{d}{1-bx}
$,
write
$F(x)
=\dfrac{1+5x}{1-x-x^2}
=(1+5x)\big(\dfrac{c}{1-ax}+\dfrac{d}{1-bx}\big)
$,
and get the power series for
$F(x)$
using
$\dfrac{1}{1-rx}
=\sum_{j=0}^{\infty} r^j x^j
$.
Have at it.
If $\alpha^k\le f_k\le \beta^k$ and $\alpha^{k+1}\le f_{k+1}\le \beta^k$, then $$f_{k+2}=f_k+f_{k+1}\ge \alpha^k+\alpha^{k+1}=\alpha^{k+2}\cdot(\frac1{\alpha^2}+\frac1\alpha)$$
and
$$f_{k+2}=f_k+f_{k+1}\le \beta^k+\beta^{k+1}=\beta^{k+2}\cdot(\frac1{\beta^2}+\frac1\beta),$$
so in order to conclude
$$\alpha^{k+2}\le f_{k+2}\le \beta^{k+2} $$
is is sufficent to have $\frac1{\alpha^2}+\frac1\alpha\ge 1$ and $\frac1{\beta^2}+\frac1\beta\le 1$. You can verify that this is indeed true for $\alpha=\frac32$ and $\beta=2$.
Best Answer
One key number-theoretical reason for starting the sequence $(0,1)$ instead of $(1,1)$ is that it makes the divisibility property of the Fibonacci sequence more straightforward to state; i.e., that $F_k$ divides $F_{nk}$ for any $k,n$. If you start with $F_0=1$ instead of $F_0=0$ then this breaks down (for instance, in that numbering $F_2=2$ but $F_4=5$) and a lot of results have to be presented with indices shifted. This has to do, roughly with the representation of $F_n$ as $\frac{1}{\sqrt{5}}\left(\phi^n-\varphi^n\right)$ (with $\varphi=\frac{1}{\phi} = \phi-1$); the fact that the exponents 'match up' with the index leads to straightforward arguments for the various divisibility properties.