# Thread: I need help with a proof (by rewriting)

1. ## I need help with a proof (by rewriting)

Hi there, because I got the comment that my descriptions weren't too good, I will copy the assignment exactly.

"9.3 F(c*(n+1)) / F(n+1) is an integer. Proof this by rewriting the quotient. F is the Fibonacci sequence so you can use F(n+2) = F(n+1) + F(n) and/or F(n+c) = F(c)F(n+1) + F(c-1)F(n)"

Well, I got stuck. I am trying and trying for over 2 hours now, but I just don't seem to see it. Can someone help me?

2. Originally Posted by MaryB
Hi there, because I got the comment that my descriptions weren't too good, I will copy the assignment exactly.

"9.3 F(c*(n+1)) / F(n+1) is an integer. Proof this by rewriting the quotient. F is the Fibonacci sequence so you can use F(n+2) = F(n+1) + F(n) and/or F(n+c) = F(c)F(n+1) + F(c-1)F(n)"

Well, I got stuck. I am trying and trying for over 2 hours now, but I just don't seem to see it. Can someone help me?
I guess 9.3 is just the number of the question, right?...

You can prove this by induction on $\displaystyle c$ using your second formula. Let $\displaystyle n$ be fixed. Let $\displaystyle c\geq 1$. Assume that $\displaystyle F(cn)=k F(n)$ where $\displaystyle k$ is an integer, and deduce that $\displaystyle F((c+1)n)=k' F(n)$ (where $\displaystyle k'\in\mathbb{N}$) from the formula $\displaystyle F((c+1)n)=F(n+cn)=F(cn)F(n+1)+F(cn-1)F(n)$ and the assumption.

3. Originally Posted by Laurent
I guess 9.3 is just the number of the question, right?...
Thank you! I get it now!
Yeah, I got the assignments by email so I just copied it directly.
Thanks again