-3
$\begingroup$

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$

$\endgroup$

closed as off-topic by YuiTo Cheng, Sil, Lord Shark the Unknown, Cesareo, Shailesh Jun 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.

  • $\begingroup$ Welcome to Math Stack Exchange. Please use MathJax $\endgroup$ – J. W. Tanner Jun 16 at 4:50
  • $\begingroup$ Please add context to your question and show your work. $\endgroup$ – Toby Mak Jun 16 at 6:22
1
$\begingroup$

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}}.$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the help! $\endgroup$ – user70197 Jun 16 at 5:35
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the help! $\endgroup$ – user70197 Jun 16 at 5:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.