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 {F(n)} that can be defined as F(1) = 1, F(2) = 1, F(n+2) = F(n) + F(n+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 X(n) (where n is any natural number), in which each digit is either 0 or 1, set by the following rules:

(i) X(1) = 1

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

For example, X(1) = 1, X(2) = 10, X(3) = 101, X(4) = 10110, X(5) = 10110101, ...

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

(2) What is B(n), which is how many times '01' appears in X(n)? For example, B(1) = 0, B(2) = 0, B(3) = 1, B(4) = 1, B(5) = 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)

X(1) = 1, X(2) = 10, X(3) = 101, X(4) = 10110, X(5) = 10110101, ...

therefore: A(1) = 1, A(2) = 2, A(3) = 3, A(4) = 5, A(5) = 8,...

recall fibonacci numbers F(n): 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))

>Will there ever be a Mathematics and Madoka page?
You can make one in the Speculah category (and link it from the Articles page) if you want.
As a side note, I think we should have a science page or something given all the discussion about lolentropy from this week. Maybe make a general page "Madoka and Science" and put all that stuff there in different sections? --Homerun-chan 15:10, 8 March 2011 (UTC)