5
$\begingroup$

Question: Let $m,n\in\mathbb{N}$, prove that if $n|m$, $F_n|F_m$.

I've tried to use induction, but I don't really know where to start since there's $2$ numbers: $n$ and $m\ \dots$ I did induction before with just $1$ number, like proving $1+2+\cdots+n=\frac{n(n+1)}{2}$, that's only dealing with one number $n$, but with this I have no clue how to do it.

Can anyone give me a little hint on how to start, I don't want you to do whole problem for me but can I have some hint so I know where to start?

Thanks for the help!

|cite|improve this question
$\endgroup$
  • 4
    $\begingroup$ Is $F_n$ the $n^{th}$ Fibonacci number? You should use only $F$ or $f$ if they are the same thing. $\endgroup$ – Git Gud May 1 '13 at 11:19
  • $\begingroup$ From Lemma# 4 of fq.math.ca/Scanned/4-3/halton.pdf, $(F_m,F_n)=F_{(m,n)}$ $\endgroup$ – lab bhattacharjee May 1 '13 at 11:53
7
$\begingroup$

Hint: Try to prove that $f_{n+m}=f_{n-1}\ f_m+f_n\ f_{m+1}$.

Then, let $m=n\times k$ for some $k\in \mathbb{N}$.

Now, prove that $f_m$ is divisible $f_n$ by induction on $k$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I think I got it, appreciated for help! $\endgroup$ – Charles G May 1 '13 at 11:38
0
$\begingroup$

You can prove the desired result without induction using Binet's formula, $$F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}$$ where $\varphi$ and $\psi$ are the roots of $x^2 + x + 1$, and the factoring identity $$a^n - b^n = (a - b)(a^{n-1} + a^{n-2}b + a^{n-3}b^2 + \cdots + ab^{n-2} + b^{n-1}).$$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Does this mean that: $$ψ = \frac{1 - \sqrt{5}}{2} = φ - \frac{\sqrt{20}}{2}$$ $\endgroup$ – Feeds Sep 24 '17 at 4:20
  • $\begingroup$ @user477343 You should be able to answer that yourself. $\endgroup$ – Maurice P Sep 24 '17 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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