Simplified statement:

The definition and general formula for Fibonacci Sequence is provided.

Define a sequence of digits \(\{X(n)\}\) in which each digit is either \(0\) or \(1\), with the following definition:

1. \(X(1) = 1\)
2. \(X(n + 1)\) is obtained from \(X(n)\) by replacing all \(0\) digits to \(1\) and all \(1\) digits to \(10\)

For example, \(X(2) = 10, X(3) = 101, X(4) = 10110, X(5) = 10110101, \dots\)

Anecdote: can be considered a clever analogy to the show, where Episode 10 should replaces Episode 1 and Episode 1 replaces Episode 0 in the viewer's next viewing

Give a general formula to:

1. \(A(n)\), the number of digits in \(X(n)\)
2. \(B(n)\), the number of times '\(01\)' appears in \(X(n)\)

Solution:

First I'll give a prove for the general formula of Fibonacci Sequence, and extend this method for the question.

For convenience, Fibonacci Sequence is defined as following, which is a bit different to the usual one:

1. \(F(0) = 0\)
2. \(F(1) = 1\)
3. \(F(n) = F(n - 1) + F(n - 2)\) for \(n \ge 2\)

Similar to linear ODE, we can solve this by finding the homogenous solution, then a particular solution, and finally substitute the initial conditions to get the general formula.

Characteristic equation: $$ \lambda^2 - \lambda - 1 = 0 \implies \lambda = \frac{1 \pm \sqrt{5}}{2} $$ Thus, the general solution is $$ U(n) = A \left(\frac{1 + \sqrt{5}}{2}\right)^n + B \left(\frac{1 - \sqrt{5}}{2}\right)^n $$ Using the initial conditions, we substitute and solve for \(A\) and \(B\), $$A = \frac{1}{\sqrt{5}}, B = -\frac{1}{\sqrt{5}}$$ Thus, we have the general formula for Fibonacci sequence $$ U(n) = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right] $$ Now, notice that we can express \(A(n) = A_0(n) + A_1(n)\), where \(A_0(n)\) and \(A_1(n)\) represents the number of \(0\) and \(1\) digits in \(A(n)\). Using the definition of \(X(n)\), this gives us the recurrence relation $$ A_0(n) = A_1(n - 1) $$ $$ A_1(n) = A(n - 1) = A_0(n - 1) + A_1(n - 1) $$ $$ \implies A_1(n) = A_1(n - 2) + A_1(n - 1) \text{ and } A_0(n) = A_0(n - 2) + A_0(n - 1) $$ If you also check the initial conditions, it is quite easy to tell that \(A_0(n) = F(n - 1)\) and \(A_1(n) = F(n)\). Thus we have $$ A(n) = F(n - 1) + F(n) = F(n + 1) = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right)^{n+1} - \left( \frac{1-\sqrt{5}}{2} \right)^{n+1} \right] $$ As for \(B(n)\), the key observation is that there can never be '\(00\)' in any \(X(n)\) and \(X(n)\) ends with \(0\) if and only if n is even. Using these facts, we can construct the formula for \(B(n)\). $$ B(n) = A_0(n) - n \% 2 = F(n - 1) - n \% 2, \text{ where \(\%\) is modulus operator} $$ In a more mathematical way, we can write this as $$ B(n) = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right)^{n-1} - \left( \frac{1-\sqrt{5}}{2} \right)^{n-1} \right] + \frac{1 - (-1)^n}{2} $$

Solve the following indefinite integrations: $$ \int{\frac{\arcsin^3(x)}{\sqrt{1 - x^2}}} dx $$ $$ \int{x \ln(x^2 + y)} dx $$ $$ \int{\frac{x^3 + 2x^2 + 10x}{x^2 - x + 1}} dx $$

Let \(u = \arcsin(x), du = \frac{dx}{\sqrt{1 - x^2}}\) $$ \begin{aligned} \int{\frac{\arcsin^3(x)}{\sqrt{1 - x^2}}} dx &= \int{u^3} du \\ &= \frac{u^4}{4} + c \\ &= \frac{\arcsin^4(x)}{4} + c \end{aligned} $$

Let \(u = x^2 + y, du = 2xdx\) $$ \begin{aligned} \int{x \ln(x^2 + y)} dx &= \frac{1}{2}\int{\ln(u)}du \\ &= \frac{1}{2}(u - u\ln(u)) + c \\ &= \frac{1}{2}(x^2 + y - (x^2 + y)\ln(x^2 + y)) + c \\ &= \frac{1}{2}(x^2 - (x^2 + y)\ln(x^2 + y)) + C \\ \end{aligned} $$

$$ \begin{aligned} \int{\frac{x^3 + 2x^2 + 10x}{x^2 - x + 1}} dx &= \int{(x + 3 + \frac{12x - 3}{x^2 - x + 1})}dx \\ &= \int{(x + 3 + 6\frac{2x - 1}{x^2 - x + 1} + \frac{3}{(x - \frac{1}{2})^2 + \frac{3}{4}})}dx \\ &= \frac{1}{2}x^2 + 3x + 6 \ln(x^2 - x + 1) + 2\sqrt{3}\arctan\left(\frac{2x - 1}{\sqrt{3}}\right) + c \end{aligned} $$