Skip to main content
Mathematics

Return to Answer

replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

Here is a late answer using my favorite Fibonacci technique.

The matrix formulation for the Fibonacci sequence is well worth knowing and easily provedeasily proved: $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n= \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$

Let $ A=\begin{pmatrix}1&1\\1&0\end{pmatrix} $. Since the second column of $A^{2k}$ is $\begin{pmatrix}F_{2k}\\F_{2k-1}\end{pmatrix}$, the second column of $$ S = A^2 + A^4 + \cdots + A^{2n} $$ contains exactly the sums we're interested in.

We have $(A^2-I)S=A^{2n+2}-A^2$. Since $A^2=A+I$ (the Fibonacci recurrence!), we get $AS=A^{2n+2}-A^2$ and so $$ S=A^{2n+1}-A =\begin{pmatrix}F_{2n+2}&F_{2n+1}\\F_{2n+1}&F_{2n}\end{pmatrix} -\begin{pmatrix}1&1\\1&0\end{pmatrix} =\begin{pmatrix}*&F_{2n+1}-1\\*&F_{2n}\end{pmatrix} $$ as claimed. This also explains where the $-1$ comes from.

Here is a late answer using my favorite Fibonacci technique.

The matrix formulation for the Fibonacci sequence is well worth knowing and easily proved: $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n= \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$

Let $ A=\begin{pmatrix}1&1\\1&0\end{pmatrix} $. Since the second column of $A^{2k}$ is $\begin{pmatrix}F_{2k}\\F_{2k-1}\end{pmatrix}$, the second column of $$ S = A^2 + A^4 + \cdots + A^{2n} $$ contains exactly the sums we're interested in.

We have $(A^2-I)S=A^{2n+2}-A^2$. Since $A^2=A+I$ (the Fibonacci recurrence!), we get $AS=A^{2n+2}-A^2$ and so $$ S=A^{2n+1}-A =\begin{pmatrix}F_{2n+2}&F_{2n+1}\\F_{2n+1}&F_{2n}\end{pmatrix} -\begin{pmatrix}1&1\\1&0\end{pmatrix} =\begin{pmatrix}*&F_{2n+1}-1\\*&F_{2n}\end{pmatrix} $$ as claimed. This also explains where the $-1$ comes from.

Here is a late answer using my favorite Fibonacci technique.

The matrix formulation for the Fibonacci sequence is well worth knowing and easily proved: $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n= \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$

Let $ A=\begin{pmatrix}1&1\\1&0\end{pmatrix} $. Since the second column of $A^{2k}$ is $\begin{pmatrix}F_{2k}\\F_{2k-1}\end{pmatrix}$, the second column of $$ S = A^2 + A^4 + \cdots + A^{2n} $$ contains exactly the sums we're interested in.

We have $(A^2-I)S=A^{2n+2}-A^2$. Since $A^2=A+I$ (the Fibonacci recurrence!), we get $AS=A^{2n+2}-A^2$ and so $$ S=A^{2n+1}-A =\begin{pmatrix}F_{2n+2}&F_{2n+1}\\F_{2n+1}&F_{2n}\end{pmatrix} -\begin{pmatrix}1&1\\1&0\end{pmatrix} =\begin{pmatrix}*&F_{2n+1}-1\\*&F_{2n}\end{pmatrix} $$ as claimed. This also explains where the $-1$ comes from.

added 24 characters in body
Source Link
lhf
lhf
  • 222.9k
  • 20
  • 254
  • 586

Here is a late answer, just for fun using my favorite Fibonacci technique.

The matrix formulation for the Fibonacci sequence is well worth knowing and easily proved: $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n= \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$

Let $ A=\begin{pmatrix}1&1\\1&0\end{pmatrix} $. Since the second column of $A^{2k}$ is $\begin{pmatrix}F_{2k}\\F_{2k-1}\end{pmatrix}$, the second column of $$ S = A^2 + A^4 + \cdots + A^{2n} $$ contains exactly the sums we're interested in.

We have $(A^2-I)S=A^{2n+2}-A^2$. Since $A^2=A+I$ (the Fibonacci recurrence!), we get $AS=A^{2n+2}-A^2$ and so $$ S=A^{2n+1}-A =\begin{pmatrix}F_{2n+2}&F_{2n+1}\\F_{2n+1}&F_{2n}\end{pmatrix} -\begin{pmatrix}1&1\\1&0\end{pmatrix} =\begin{pmatrix}*&F_{2n+1}-1\\*&F_{2n}\end{pmatrix} $$ as claimed. This also explains where the $-1$ comes from.

Here is a late answer, just for fun.

The matrix formulation for the Fibonacci sequence is well worth knowing and easily proved: $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n= \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$

Let $ A=\begin{pmatrix}1&1\\1&0\end{pmatrix} $. Since the second column of $A^{2k}$ is $\begin{pmatrix}F_{2k}\\F_{2k-1}\end{pmatrix}$, the second column of $$ S = A^2 + A^4 + \cdots + A^{2n} $$ contains exactly the sums we're interested in.

We have $(A^2-I)S=A^{2n+2}-A^2$. Since $A^2=A+I$ (the Fibonacci recurrence!), we get $AS=A^{2n+2}-A^2$ and so $$ S=A^{2n+1}-A =\begin{pmatrix}F_{2n+2}&F_{2n+1}\\F_{2n+1}&F_{2n}\end{pmatrix} -\begin{pmatrix}1&1\\1&0\end{pmatrix} =\begin{pmatrix}*&F_{2n+1}-1\\*&F_{2n}\end{pmatrix} $$ as claimed. This also explains where the $-1$ comes from.

Here is a late answer using my favorite Fibonacci technique.

The matrix formulation for the Fibonacci sequence is well worth knowing and easily proved: $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n= \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$

Let $ A=\begin{pmatrix}1&1\\1&0\end{pmatrix} $. Since the second column of $A^{2k}$ is $\begin{pmatrix}F_{2k}\\F_{2k-1}\end{pmatrix}$, the second column of $$ S = A^2 + A^4 + \cdots + A^{2n} $$ contains exactly the sums we're interested in.

We have $(A^2-I)S=A^{2n+2}-A^2$. Since $A^2=A+I$ (the Fibonacci recurrence!), we get $AS=A^{2n+2}-A^2$ and so $$ S=A^{2n+1}-A =\begin{pmatrix}F_{2n+2}&F_{2n+1}\\F_{2n+1}&F_{2n}\end{pmatrix} -\begin{pmatrix}1&1\\1&0\end{pmatrix} =\begin{pmatrix}*&F_{2n+1}-1\\*&F_{2n}\end{pmatrix} $$ as claimed. This also explains where the $-1$ comes from.

Source Link
lhf
lhf
  • 222.9k
  • 20
  • 254
  • 586

Here is a late answer, just for fun.

The matrix formulation for the Fibonacci sequence is well worth knowing and easily proved: $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n= \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$

Let $ A=\begin{pmatrix}1&1\\1&0\end{pmatrix} $. Since the second column of $A^{2k}$ is $\begin{pmatrix}F_{2k}\\F_{2k-1}\end{pmatrix}$, the second column of $$ S = A^2 + A^4 + \cdots + A^{2n} $$ contains exactly the sums we're interested in.

We have $(A^2-I)S=A^{2n+2}-A^2$. Since $A^2=A+I$ (the Fibonacci recurrence!), we get $AS=A^{2n+2}-A^2$ and so $$ S=A^{2n+1}-A =\begin{pmatrix}F_{2n+2}&F_{2n+1}\\F_{2n+1}&F_{2n}\end{pmatrix} -\begin{pmatrix}1&1\\1&0\end{pmatrix} =\begin{pmatrix}*&F_{2n+1}-1\\*&F_{2n}\end{pmatrix} $$ as claimed. This also explains where the $-1$ comes from.