# Thread: some problem in strong induction

1. ## some problem in strong induction

hi

here is a problem i am trying to do.

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

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

let

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

let m be arbitrary in N. so the goal is

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

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

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

since we have to prove P(n), suppose

$\displaystyle m\lvert n$

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

now

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

so using inductive hypothesis, it follows that

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

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

$\displaystyle 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

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

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

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

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

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

$\displaystyle (n-m)<n$

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 ?

2. ## Re: some problem in strong induction

I learned through some other forums that we have to have the condition

$\displaystyle m>0\quad n>0$

after that the proof is easy