Question

Linear Algebra:

Define the fibonnaci sequence as such:
F(0) = 0
F(1) = 1
for all n > 1, F(n) = F(n-1) + F(n-2)

Prove this statement with induction:
Using proof by induction:

Answer 1

If
\[Q = \left[\begin{matrix}F_{2} & F_{1} \\ F_{1} & F_{0}\end{matrix}\right] = \left[\begin{matrix}1 & 1 \\ 1 & 0\end{matrix}\right]\]
Then
\[Q^{n} = \left[\begin{matrix}F_{n+1} & F_{n} \\ F_{n} & F_{0}\end{matrix}\right]\]

Answer 2

Let
\[P(n) = Q^{n}\]
Then
\[P(1) = Q^{1} = \left[\begin{matrix}F_{1+1} & F_{1} \\ F_{1} & F_{0}\end{matrix}\right] = \left[\begin{matrix}1 & 1 \\ 1 & 0\end{matrix}\right] \]
And assuming P(n) is true,
\[P(n+1) = Q^{n+1} = Q^{n}Q^{1} = \left[\begin{matrix}F_{n+1} & F_{n} \\ F_{n} & F_{0}\end{matrix}\right]\left[\begin{matrix}1 & 1 \\ 1 & 0\end{matrix}\right] = \left[\begin{matrix}F_{n+1}+F_{n} & F_{n+1} \\ F_{n+1}+F_{0} & F_{n}\end{matrix}\right] \]
\[= \left[\begin{matrix}F_{n+2} & F_{n+1} \\ F_{n+1} & F_{n}\end{matrix}\right]\]
but from the last equation, the bottom-right entry should be F_{0} not F_{n} so I don't know what happened.

Answer 3

@Narad He can help in Linear Algebra

Answer 4

Looking at this: https://math.stackexchange.com/questions/867394/how-to-compute-the-nth-number-of-a-general-fibonacci-sequence-with-matrix-multip
I feel like the textbook I'm using is wrong, and I'm right xd

Answer 5

Hey man, after all, textbooks are written by humans and our intellect rules over that textbook. Who knows, maybe it is wrong! xD

Answer 6

Based on this website, I'm also right and the textbook is wrong:
https://www.slader.com/textbook/9781118473504-elementary-linear-algebra-11th-edition/51/technology-exercises/3/

I'm going to contact my classmates to see if they noticed.

Answer 7

Wait no I messed up on the bottom-left entry

Answer 8

\(\color{#0cbb34}{\text{Originally Posted by}}\) @mhchen

And assuming P(n) is true,
\[P(n+1) = Q^{n+1} = Q^{n}Q^{1} = \left[\begin{matrix}F_{n+1} & F_{n} \\ F_{n} & F_{0}\end{matrix}\right]\left[\begin{matrix}1 & 1 \\ 1 & 0\end{matrix}\right] = \left[\begin{matrix}F_{n+1}+F_{n} & F_{n+1} \\ F_{n}+F_{0} & F_{n}\end{matrix}\right] \]
\[= \left[\begin{matrix}F_{n+2} & F_{n+1} \\ F_{n} & F_{n}\end{matrix}\right]\]

\(\color{#0cbb34}{\text{End of Quote}}\)

Answer 9

I hate matrixes

Answer 10

The teacher confirmed, textbook was wrong

Answer 11

you gotta know your smart, when you find an error with the textbook