0

Im stuck on this question, i have to prove that $$\frac{F_n-F_{n+16}}{7}$$ is always an odd integer. I tried induction to do this but i just can't see how to prove it.

thanks for any help

Adi Dani
  • 16,949
Madmarkshero
  • 47
  • 3
    Is it true? It might be true that it is an integer, but I don't see how it could be true that it is always odd, since $$\frac{F_2-F_{18}}{7} = \frac{F_1-F_{17}}{7} + \frac{F_0-F_{16}}{7}$$ – Thomas Andrews Nov 11 '13 at 20:19
  • The divisibility by seven can be explained by studying the periodicity of the sequence of residues of the Fibonacci numbers. There are plenty of good questions and answers covering that on this site. But why do you claim that this is odd? $$\frac{F_{17}-F_1}7=\frac{1597-1}7=228?$$ – Jyrki Lahtonen Nov 11 '13 at 20:19
  • This can't be correct as written. The Fibonacci numbers mod two go 'odd, odd, even, odd, odd, even', and since $16\bmod 3=1$, the difference of two Fibonacci numbers 16 apart might be the difference of two odd numbers (and thus even). – Steven Stadnicki Nov 11 '13 at 20:20
  • There is an explicit formula for $F(n)$, i.e., a solution for the recurrence $F(n+1)= F(n) + F(n-1)$. Can you use it? – Jas Ter Nov 11 '13 at 20:22
  • And you do need to use two previous values in an induction hypothesis. This holds for all proofs by induction related to Fibonaccis. Note that the base case must then also handle two smallest values of $n$. No need to think in terms of periodicity of the sequence of residues as I initially thought. – Jyrki Lahtonen Nov 11 '13 at 20:22

1 Answers1

1

I suspect that, instead, you are merely supposed to show that $$\frac{F_n-F_{n+16}}7$$ is an integer for all $n$. As discussed in the comments above, the integer needn't be odd.

I leave the two base cases to you (we need two of them for an induction proof).

Now, let's suppose that $$\frac{F_n-F_{n+16}}7$$ and $$\frac{F_{n+1}-F_{(n+1)+16}}7$$ are both integers for some $n$. Note, then, that

$$\begin{align*} \frac{F_{n+2}-F_{(n+2)+16}}7&=\frac{(F_n+F_{n+1})-(F_{n+16}+F_{(n+1)+16})}7\\\\ &=\frac{F_n-F_{n+16}}7+\frac{F_{n+1}-F_{(n+1)+16}}7\;. \end{align*}$$

Brian M. Scott
  • 616,228
Cameron Buie
  • 102,994