Question
Solve the recurrence equation
\( a_n = a_{n-1}+2a_{n-2} \)
with
\( a_0 = 0 \)
and
\( a_1 = 1 \).
ans
Get eigenvalues.
\(
a_n - a_{n-1}-2a_{n-2}=0
\)
\(
\rightarrow
\alpha^2 -\alpha - 2 = 0
\)
\(
\rightarrow
\alpha = -1 \text{ or } 2
\)
\(
a_n = c_1(-1)^n + c_2(2)^n
\)
\(
\Rightarrow
\begin{cases}
a_0 = 0 = c_1(-1)^0 + c_2(2)^0 \\
a_1 = 1 = c_1(-1)^1 + c_2(2)^1
\end{cases}
\)
\(
c_1 = -\frac{1}{3},
\;
c_2 = \frac{1}{3}
\)
\(
\therefore
a_n =
-\frac{1}{3}(-1)^n
+\frac{1}{3}(2)^n
,\; n\geq 0\)
Question
Let \( a_n \) denote the number of bit strings
of length \( n \) that do not have two
consecutive 0's.
Let \( A \) denote the set of bit strings
without two consecutive 0's.
- Find a recurrence relation for \( a_n \).
- Give initial conditions for \( a_n \).
- Solve the recurrence relation for \( a_n \).
ans
\( a_n \)代表在長度n時的方法數。
-
討論第n個bit的可能
- 第\( n \) bit為0:
那第\( n-1 \) bit 就不能為0,方法數為1，那\( n-2 \)項之前的bit不含有連續的0即可，則討論為\( 1\cdot a_{n-2} \)
- 討論討論第n項bit為1，那只要\( n-1 \)之前的bit不含連續0就行了。
即為\( a_{n-1} \)
- 最後得出\( a_n = a_{n-1} + a_{n-2} \)
-
當只有一個位數時，顯然不會有連續的0。方法數為2。\( a_1 = 2 \),當有兩位數時，可能bit為11, 01, 10，三種可能，\( a_2 = 3 \)，當有三位數時，就要討論第三位數為1或0，即\( a_n = a_{n-1}+a_{n-2} \)的遞迴情況，所以intial condition 為\( a_1 = 2,\;a_2 = 3 \)。
-
為Fibonacci向右移兩項，
\(
\Rightarrow
a_n=F_{n+2}
=
\frac{1}{\sqrt{5}}
[(\frac{1+\sqrt{5}}{2})^{(n+2)}-(\frac{1+\sqrt{5}}{2})^{(n+2)}], \; n\geq 1
\)