The fibonacci sequence is defined as x0 = 0, x1 = 1 and xn+2 = xn +xn+1 , for all non negative integers n prove that, xm = xr+1xm-r + xrxm-r for all integers m ≥ 1 and 0 ≤ r ≤ m-1 and xd divides xkd for all integers k and d
The Answer to the Question
is below this banner.
Here's the Solution to this Question
Let's simplify this statement:
(*). Let's prove it using the induction by r and m simultaneously. Let's prove it for every m(so m is fixed).
Since , the base of induction is:
Since , we obtain that . Thus, we should check if . Hence, we proved the base of induction.
Now, we will assume, that the (*) is true for every . Let's prove it for :
Let's prove the base of induction(by r):
a) Hence, we should check if:
b) The induction assumption is that for every , such that: , (*) is true. Let's prove it for We should check the following:
We can apply the induction assumption to both of the summands in the following way:
For the first summand:
, and we obtain the following(by using the (*)): . By applying the induction assumption and (*) to the second summand we obtain: Thus we should check if: This is true.
2. where are some integers.
Let's use the previous statement:
By applying this fact times, we obtain the following: