User talk:Prima

Will there ever be a Mathematics and Madoka page?

Fibonacci sequence question that appeared in Episode 9

This advanced Algebra problem previously appeared in the 2003 Tokyo entrance exam:

The text reads: A number sequence {Fn} that can be defined as F1 = 1, F2 = 1, Fn+2 = Fn + Fn+1 (where n is any natural number) is called the Fibonacci sequence and its general solution is given by,

Answer the following questions by using this fact if needed:

Define a sequence of natural numbers Xn (where n is any natural number), in which each digit is either 0 or 1, set by the following rules:

(i) X1 = 1

(ii) We define Xn+1 as a natural number, which can be gotten by replacing the digits of Xn with 1 if the digit is 0, and with 10 if the digit is 1.

For example, X1 = 1, X2 = 10, X3 = 101, X4 = 10110, X5 = 10110101, ...

(1) What is An, which is the number of digits of Xn?

(2) What is Bn, which is how many times '01' appears in Xn? For example, B1 = 0, B2 = 0, B3 = 1, B4 = 1, B5 = 3,...

Solution

Part (1)

Let A(n) equal to the number of digits in X(n), which consists solely of 1s and 0s. Let's suppose x(n) is the number of 0s in X(n) at n iteration (poor choice of variable by the student). Let's suppose y(n) is the number of 1s in X(n) at n iteration.

1) Every time a 0 appears, it is replaced with 1 at the next iteration.

2) Every time a 1 appears, it is replaced with 10 at t he next iteration.

Therefore, the number of 0s in the next iteration is equal to the number of 1s previously:

x(n+1)= y(n)

and the number of 1s in the next iteration is equal to the number of 0s AND the numbers of 1s previously:

y(n+1)=x(n)+y(n)

Prove: x(n) is a fibonacci sequence:

i) y(n+1) = x(n) + y(n)

ii) x(n+2) = y(n+1)

iii) x(n+1) = y(n)

complete the substition shows:

x(n+2) = y(n+1) = x(n) + y(n) = x(n) + x(n+1)

x(n+2) = x(n+1) + x(n) ie definition of fibonacci sequence

Since x(n) is a fibonacci sequence, y(n) is also a fibonacci sequence since x(n+1) = y(n). Therefore:

x(n+2)=x(n+1)+x(n)

y(n+2)=y(n+1)+y(n)

x(n+2)+y(n+2)=x(n+1)+y(n+1)+x(n)+y(n)

Recall: A(n)=x(n)+y(n), therefore

A(n+2)=A(n+1)+A(n)

X1 = 1, X2 = 10, X3 = 101, X4 = 10110, X5 = 10110101, ...

therefore: A1 = 1, A2 = 2, A3 = 3, A4 = 5, A5 = 8,...

recall fibonacci numbers f: 1, 1, 2, 3, 5, 8. Therefore A(n) = F(n+1):

Part (2)

Let B(n) be the number of times '01' appears in X(n).

Any two digits in X(n) may be 00, 01, 10, 11

the corresponding digits in the next iteration X(n+1) will be

00 -> 11

01 -> 110

10 -> 101

11 -> 1010

Thus, any '1*' sequence in X(n) will contribute to a 01 sequence in the next iteration. In other words, B(n+1) equals y(n), except when unit digit of X(n) =1, or:

B(n+1) = y(n) - odd(X(n))

y(n) is a fibonacci sequence (see Part (1) for proof) with starting values: y(1)=1, y(2)=1, y(3)=2 thus y(n) =f(n)

B(n+1) = f(n) - odd(X(n)) = 'big equation' - odd(X(n)), therefore B(n) = F(n-1) - odd(X(n-1))