0
$\begingroup$

Statement: Proof by induction for all $n\geq 1$

$$\begin{pmatrix}F_n\\F_{n+1}\end{pmatrix}=\begin{pmatrix}0 & 1\\\ 1 & 1\end{pmatrix}^{n-1}\begin{pmatrix}1\\1\end{pmatrix}$$

I'm know the induction steps but i keep having troubles with the use of induction in matrices. Im verified for n=1 and assumed n=k. But can't proced after assume that work for k+1.

I'm stuck in k+1 step.

$$\begin{pmatrix}F_{k+1}\\F_{k+2}\end{pmatrix}=\begin{pmatrix}0 & 1\\\ 1 & 1\end{pmatrix}^{k}\begin{pmatrix}1\\1\end{pmatrix}$$

I tried too

$$\begin{pmatrix}F_k+F_{k-1}\\F_{k+1}+F_k\end{pmatrix}=\begin{pmatrix}0 & 1\\\ 1 & 1\end{pmatrix}^{k}\begin{pmatrix}1\\1\end{pmatrix}$$

but idk how to procede

$\endgroup$
2
  • $\begingroup$ What have you tried, and what are you stuck on? $\endgroup$ Commented Dec 15, 2023 at 3:51
  • $\begingroup$ I edit my question to show what i tried and what i'm stucked. $\endgroup$ Commented Dec 15, 2023 at 4:00

1 Answer 1

Reset to default
4
$\begingroup$

Because $\begin{pmatrix}0 & 1\\\ 1 & 1\end{pmatrix}\begin{pmatrix}a\\b\end{pmatrix} =\begin{pmatrix}b\\a+b\end{pmatrix} $.

(added later)

Therefore, and this is the induction step,

$\begin{pmatrix}0 & 1\\\ 1 & 1\end{pmatrix}\begin{pmatrix}F_n\\F_{n+1}\end{pmatrix} =\begin{pmatrix}F_{n+1}\\F_n+F_{n+1}\end{pmatrix} =\begin{pmatrix}F_{n+1}\\F_{n+2}\end{pmatrix} $.

This needs to be combined with

$\begin{pmatrix}0 & 1\\\ 1 & 1\end{pmatrix} \begin{pmatrix}0 & 1\\\ 1 & 1\end{pmatrix}^n =\begin{pmatrix}0 & 1\\\ 1 & 1\end{pmatrix}^{n+1} $.

$\endgroup$
3
  • $\begingroup$ I didn't get the idea. That's basically what I'm trying to demonstrate, isn't it? $\endgroup$ Commented Dec 15, 2023 at 4:01
  • 1
    $\begingroup$ No. This is a matrix multiplication identity. It allows you to carry the induction step through. $\endgroup$ Commented Dec 15, 2023 at 4:29
  • $\begingroup$ I think i get the idea. Thanks $\endgroup$ Commented Dec 15, 2023 at 10:31

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.