# Show that $a_{n-1}$ divides $a_{kn-1}$ for recurrence relation $a_n = a_{n-1} + a_{n-2}$ [closed]

Question is posted above will be super thankful for all your help

$$a_n = a_{n-1} + a_{n-2}$$

Show that $$a_{n-1}$$ divides $$a_{kn-1}$$for recurrence relation above

$$a_1 = 1$$ $$a_2 = 2$$ $$a_3 = 3$$

## closed as off-topic by YuiTo Cheng, Sil, Lord Shark the Unknown, Cesareo, ShaileshJun 24 at 11:07

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – YuiTo Cheng, Sil, Lord Shark the Unknown, Cesareo, Shailesh
If this question can be reworded to fit the rules in the help center, please edit the question.

• Welcome to Math Stack Exchange. Please use MathJax – J. W. Tanner Jun 16 at 4:50

These, of course are Fibonacci numbers. The recurrence means that $$\pmatrix{0&1\\1&1}\pmatrix{a_n\\a_{n+1}}=\pmatrix{a_{n+1}\\a_{n+2}}.$$ Write $$M=\pmatrix{0&1\\1&1}$$ Then, by induction, $$\pmatrix{a_n\\a_{n+1}}=M^{n-1}\pmatrix{a_1\\a_2}=M^{n-1}\pmatrix{1\\2} =M^n\pmatrix{1\\1}=M^{n+1}\pmatrix{0\\1}=M^{n+2}\pmatrix{1\\0}.$$ In the matrix $$M^n$$ the first column is $$M^n\pmatrix{1\\0}=\pmatrix{a_{n-2}\\a_{n-1}}$$ and the second column is $$M^n\pmatrix{0\\1}=\pmatrix{a_{n-1}\\a_n}.$$ Therefore $$M^n=\pmatrix{a_{n-2}&a_{n-1}\\a_{n-1}&a_n}.$$ So $$M^n\equiv\pmatrix{a_{n-2}&0\\0&a_n}\pmod {a_{n-1}}$$ and $$M^{kn}\equiv\pmatrix{a_{n-2}&0\\0&a_n}^k \equiv\pmatrix{a_{n-2}^k&0\\0&a_n^k}\pmod {a_{n-1}}.$$ Therefore $$a_{kn-1}\equiv 0\pmod{a_{n-1}}.$$

What is missing is that $$a_0=a_1=1$$ initial values in addition to $$a_n=a_{n-1}+a_{n-2}.$$ This implies that $$a_n = F_{n+1}$$ where $$F$$ is the famous Fibonacci sequence which is a Divisiblity sequence. That is, it satisfies $$F_n$$ divides $$F_{kn}$$ for $$n>0$$ and any integer $$k$$. This property implies your result.

• Thank you for the help! – user70197 Jun 16 at 5:35

First, we consider $$\{b_n\}$$ s.t. $$b_n=b_{n-1}+b_{n-2}$$ and $$b_0=0$$, $$b_1=1$$.

You can check $$b_{n+1}=a_n$$.

Now, it suffices to show $$b_n|b_{kn}$$. (looks more clear)

Observe that $$b_n=b_{n-1}+b_{n-2}=b_{n-2}+b_{n-3}+b_{n-2}=...$$ can be finally written as $$\alpha b_0+\beta b_1$$ where $$\alpha,\beta$$ are integers.

Here, $$b_n=\beta$$.

Now, let us use mathematical induction. Assuming $$b_n|b_{kn}$$, $$b_n|\alpha b_{kn}+\beta b_{kn+1}=b_{(k+1)n}$$.

Thus we are done.

• Thank you for the help! – user70197 Jun 16 at 5:35