Solution to The fibonacci sequence is defined as x0 = 0, x1 = 1 and xn+2 = … - Sikademy
Author Image

Archangel Macsika

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.

Can't find a solution anywhere?


Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

  1. x_m = x_{r+1}x_{m-r} + x_rx_{m-r}.

Let's simplify this statement:

x_m=x_{r+1}x_{m-r} + x_rx_{m-r} = x_{m-r}(x_{r+1} + x_r) = x_{m-r}x_{r+2} (*). Let's prove it using the induction by r and m simultaneously. Let's prove it for every m(so m is fixed).

Since m\ge 1 , the base of induction is:

m=1: x_1 = x_{1-r}x_{r+2}. Since 0 \le r \le m-1, we obtain that r = 0 . Thus, we should check ifx_1 = x_{1-0}x_{0+2} = 1\cdot 1 = 1 . Hence, we proved the base of induction.

Now, we will assume, that the (*) is true for every m<m_0. Let's prove it for m= m_0:

Let's prove the base of induction(by r):

a) r =0. Hence, we should check if: x_{m_0} = x_{m_0 -0}x_{0+2} = x_{m_0}x_2 = x_{m_0}.

b) The induction assumption is that for every r, such that: 0\le r < r_0 \le m_0 -1 , (*) is true. Let's prove it for r = r_0. We should check the following:

x_{m_0} = x_{m_0 - r_0}x_{r_0 +2} = x_{m_0 - r_0}x_{r_0 +1} + x_{m_0 - r_0}x_{r_0}. We can apply the induction assumption to both of the summands in the following way:

For the first summand:

r_0 + 1 = (r_0 -1) + 2, m_0 -r_0 = (m_0 -1) - (r_0 -1) , and we obtain the following(by using the (*)): x_{m_0 - r_0}x_{r_0 +1} = x_{m_0 -1}. By applying the induction assumption and (*) to the second summand we obtain: x_{m_0 - r_0}x_{r_0} = x_{m_0 -2}. Thus we should check if: x_{m_0} = x_{m_0 -1} + x_{m_0 -2}. This is true.

2.x_d | x_{kd}, where k,d are some integers.

Let's use the previous statement:

x_{kd} = x_{kd -d }x_{d+2} = x_{(k-1)d}x_{d+2}. By applying this fact (k-1) times, we obtain the following: x_{kd} = x_{d} x_{d+2}^{k-1}.

Thus (k \ge 1) : x_d |x_{kd}

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3964-qpid-2663