# some problem in strong induction

• Oct 4th 2011, 10:38 PM
issacnewton
some problem in strong induction
hi

here is a problem i am trying to do.

$\forall m,n \in \mathbb{N}[(m\lvert n)\Rightarrow (F_m\lvert F_n)]$

where $F_n$ is nth Fibonacci number. following is my attempt to prove.

let

$P(n)=[(m\lvert n) \Rightarrow (F_m\lvert F_n)]$

let m be arbitrary in N. so the goal is

$\forall n[(\forall k< n P(k))\Rightarrow P(n)]$

where k runs in N.so let n be arbitrary in N. suppose

$\forall k< n P(k)$ and

since we have to prove P(n), suppose

$m\lvert n$

I have proven some base cases for n=0,1,2 so the next case is
$n\geqslant 3$

now

$1\leqslant n-2 < n\quad \therefore (n-2)\in \mathbb{N}$

so using inductive hypothesis, it follows that

$m\lvert (n-2)\Rightarrow F_m\lvert F_{n-2}$

we can also come up the following conclusion for n-1,

$m\lvert (n-1)\Rightarrow F_m\lvert F_{n-1}$

but I don't know what to do with this. I thought of another approach. since I assumed that

$m\lvert n\quad \therefore \exists k\in \mathbb{Z} (mk=n)$

$\therefore mk=n \quad \because m,n\in \mathbb{N}\Rightarrow k\in\mathbb{N}$

$\therefore m(k-1)+m=n\quad \therefore m(k-1)=n-m$

$\therefore m\lvert (n-m)$

I can use this for the inductive hypothesis , but I can't be sure if

$(n-m)

because since m is arbitrary in N,m could be zero, in which case the above inequality fails.

So what approach should I take here ?
• Oct 6th 2011, 07:05 PM
issacnewton
Re: some problem in strong induction
I learned through some other forums that we have to have the condition

$m>0\quad n>0$

after that the proof is easy