TAOCP 1.2.8: Fibonacci Numbers
Section 1.2.8 exercises: 42/42 solved.
Section 1.2.8. Fibonacci Numbers
Exercises from TAOCP Volume 1 Section 1.2.8: 42/42 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [10] | simple | solved | - |
| 2 | [20] | medium | solved | - |
| 3 | [25] | medium | solved | - |
| 4 | [14] | simple | verified | 38s |
| 5 | [20] | medium | solved | - |
| 6 | [HM10] | hm-simple | verified | 36s |
| 7 | [15] | simple | solved | - |
| 8 | [15] | simple | solved | - |
| 9 | [M20] | math-medium | solved | - |
| 10 | [15] | simple | solved | - |
| 11 | [M20] | math-medium | verified | 42s |
| 12 | [M26] | math-hard | solved | - |
| 13 | [M22] | math-medium | solved | - |
| 14 | [M28] | math-hard | verified | 54s |
| 15 | [M22] | math-medium | solved | - |
| 16 | [M20] | math-medium | verified | 43s |
| 17 | [M24] | math-medium | verified | 44s |
| 18 | [20] | medium | solved | - |
| 19 | [M27] | math-hard | verified | 44s |
| 20 | [M16] | math-medium | solved | - |
| 21 | [M25] | math-medium | solved | - |
| 22 | [M20] | math-medium | solved | - |
| 23 | [M23] | math-medium | verified | 2m21s |
| 24 | [HM20] | hm-medium | solved | - |
| 25 | [M21] | math-medium | solved | - |
| 26 | [M20] | math-medium | solved | - |
| 27 | [M20] | math-medium | solved | - |
| 28 | [M21] | math-medium | solved | - |
| 29 | [M23] | math-medium | verified | 9m17s |
| 30 | [M38] | math-project | solved | - |
| 31 | [M20] | math-medium | solved | - |
| 32 | [M24] | math-medium | solved | - |
| 33 | [HM24] | hm-medium | solved | - |
| 34 | [M24] | math-medium | solved | - |
| 35 | [M24] | math-medium | solved | - |
| 36 | [M32] | math-hard | verified | 8m27s |
| 37 | [M35] | math-hard | solved | - |
| 38 | [35] | hard | solved | - |
| 39 | [M24] | math-medium | solved | - |
| 40 | [M25] | math-medium | solved | - |
| 41 | [M25] | math-medium | verified | 10m24s |
| 42 | [M26] | math-hard | solved | - |
TAOCP 1.2.8 Exercise 1
Fibonacci's original problem assumes that a pair of rabbits produces a new pair every month, starting from one newly born pair, and that rabbits become productive after one month.
TAOCP 1.2.8 Exercise 2
Equation (15) gives F_n = \frac{\phi^n}{\sqrt{5}} \text{ rounded to the nearest integer,} \qquad \phi = \frac{1+\sqrt{5}}{2}.
TAOCP 1.2.8 Exercise 3
Exercise 2 shows that F_n = \phi^n/\sqrt{5} \text{ rounded to the nearest integer,} by Eq.
TAOCP 1.2.8 Exercise 4
By Eq.
TAOCP 1.2.8 Exercise 5
We are asked to find all positive integers $n$ such that F_n = n^2.
TAOCP 1.2.8 Exercise 6
Let A=\begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}.
TAOCP 1.2.8 Exercise 7
Assume that $n$ is composite.
TAOCP 1.2.8 Exercise 8
We extend the Fibonacci sequence to negative indices by the recurrence F_{n+2} = F_{n+1} + F_n for all integers $n$.
TAOCP 1.2.8 Exercise 9
By exercise 8, the Fibonacci recurrence F_{n+2}=F_{n+1}+F_n is assumed to hold for all integers $n$.
TAOCP 1.2.8 Exercise 10
From equation (14) we have the exact expression F_n = \frac{1}{\sqrt{5}}\left(\phi^n - \hat{\phi}^n\right), where
TAOCP 1.2.8 Exercise 11
We prove the identities \phi^n = F_n \phi + F_{n-1}, \qquad \hat{\phi}^n = F_n \hat{\phi} + F_{n-1} for all integers $n$ by induction and by using the definitions in Section 1.
TAOCP 1.2.8 Exercise 12
Let \mathcal{G}(z)=\sum_{n\ge0}\mathcal{F}_n z^n be the generating function for the second order Fibonacci sequence.
TAOCP 1.2.8 Exercise 13
Let A(z)=\sum_{n\ge0} a_n z^n be the generating function for the sequence $\langle a_n\rangle$.
TAOCP 1.2.8 Exercise 14
We are asked to find a closed-form expression for the sequence $\langle a_n \rangle$ defined by a_0 = 0, \qquad a_1 = 1, \qquad a_{n+2} = a_{n+1} + a_n + \binom{n}{m}, \quad n \ge 0, where $m$ is a fi...
TAOCP 1.2.8 Exercise 15
Define d_n=c_n-xa_n-yb_n.
TAOCP 1.2.8 Exercise 16
We want to prove that \sum_{k=0}^{n} \binom{n-k}{k} = F_{n+1}.
TAOCP 1.2.8 Exercise 17
Using the conventions of exercise 8, Fibonacci numbers are extended to all integer subscripts.
TAOCP 1.2.8 Exercise 18
We are asked whether the sum of the squares of consecutive Fibonacci numbers, F_n^2 + F_{n+1}^2, is itself always a Fibonacci number.
TAOCP 1.2.8 Exercise 19
Determine the exact value of $\cos 36^\circ$.
TAOCP 1.2.8 Exercise 20
We wish to find a closed form for S_n = \sum_{k=0}^{n} F_k in terms of Fibonacci numbers.
TAOCP 1.2.8 Exercise 21
Let S_n(x)=\sum_{k=0}^{n}F_kx^k.
TAOCP 1.2.8 Exercise 22
We wish to show that \sum_{k=0}^{n} \binom{n}{k} F_{m+k} is a Fibonacci number.
TAOCP 1.2.8 Exercise 23
We restart from a clean derivation and fix the missing structural step directly.
TAOCP 1.2.8 Exercise 24
Let $D_n$ denote the determinant of the $n \times n$ matrix A_n = \begin{pmatrix} 1 & -1 & 0 & 0 & \cdots & 0 & 0 & 0 \\ 1 & 1 & -1 & 0 & \cdots & 0 & 0 & 0 \\
TAOCP 1.2.8 Exercise 25
By Eq.
TAOCP 1.2.8 Exercise 26
We start from Exercise 25, which asserts that 2^n F_n = 2 \sum_{\substack{k=1\\ k \text{ odd}}}^{\,n} \binom{n}{k} 5^{(k-1)/2}.
TAOCP 1.2.8 Exercise 27
Let $p$ be a prime with $p \ne 5$.
TAOCP 1.2.8 Exercise 28
From the closed form expression (14) for the Fibonacci numbers, we have F_n = \frac{1}{\sqrt{5}}\bigl(\phi^n - \hat{\phi}^n\bigr), \qquad \hat{\phi} = 1-\phi = \frac{1}{2}(1-\sqrt{5}).
TAOCP 1.2.8 Exercise 29
We are asked to compute Fibonomial coefficients and prove a recurrence that guarantees their integrality.
TAOCP 1.2.8 Exercise 30
Let $\langle F_n \rangle$ denote the Fibonacci sequence as defined in Section 1.
TAOCP 1.2.8 Exercise 31
We are asked to compute $F_n \phi \bmod 1$, that is, the fractional part of $F_n \phi$.
TAOCP 1.2.8 Exercise 32
We use Eq.
TAOCP 1.2.8 Exercise 33
By the addition formulas for the sine function, \sin\left(\frac{\pi}{2}+w\right)=\cos w.
TAOCP 1.2.8 Exercise 34
We prove existence and uniqueness separately.
TAOCP 1.2.8 Exercise 35
We define a **base-$\phi$ expansion** of a real number $x \ge 0$ to be a formal series x = \sum_{k=-\infty}^{n} d_k \phi^k, where each $d_k \in {0,1}$ and $n$ is an integer such that $d_n = 1$.
TAOCP 1.2.8 Exercise 36
Let S_1=\text{a},\quad S_2=\text{b},\quad S_{n+2}=S_{n+1}S_n \quad (n\ge1), so that
TAOCP 1.2.8 Exercise 37
Let a position be denoted by $(N,p)$, where $N$ is the number of chips remaining and $p$ is the number of chips removed on the preceding move.
TAOCP 1.2.8 Exercise 38
Exercise 37 defines the following game.
TAOCP 1.2.8 Exercise 39
The recurrence relation is a_{n+2}=a_{n+1}+6a_n, with initial conditions
TAOCP 1.2.8 Exercise 40
We are asked to solve the recurrence f(1)=0; \qquad f(n)=\min_{0<k<n}\max(1+f(k),\,2+f(n-k)), \qquad n>1.