I hate to say this, but...I'm stuck on an induction proof. I'm trying to prove that , where is the th Fibonacci number. I have it reduced to proving that for all . I have the rest of the proof.
So I tried proving it with induction.
It's trivial for , so I assumed . Then I tried to prove that .
Using an identity I know and have proved,
for some , but now I'm stuck.
So you can induct on m and under the induction hypothesis prove it is true for all q.
Or you can induct on q and under the induction hypothesis prove it is true for all m.
If you think carefully both prove the original statement. Atleast I'm pretty convinced.
The reason to chose 2nd approach is that the result is closely tied to induction on q rather than induction on m. It's almost trivial that way.
You may want to look at a similar post I did a few days ago -
Your original problem follows directly from the identity, I wrote there. This is just FYI