- Вправа 2.2
-
Зовнішній цикл робить $N_{max}$ ітерацій. Внутрішній $\frac{N_{max}(N_{max}-1)}{2}$. На кожній ітерації внутрішнього циклу виконується два додавання і одне ділення. В підсумку $3\frac{N_{max}^2(N_{max}-1)}{2}$.
- Вправа 2.3
-
int Cn(int n) {
if (n == 1) return 2;
return (1 + 1. / n) * Cn(n - 1) + 2;
}
- Вправа 2.6
-
\[
a_n = q \operatorname{Fib}(n-1) + p \operatorname{Fib}(n-2)
\]
- Вправа 2.7
-
\[
a_n = q \operatorname{Fib}(n-1) + p \operatorname{Fib}(n-2) + r \operatorname{Fib}(n-2)
\]
p, q, p + q + r, p + 2q + r, 2p + 3q + 2r, 3p + 5q + 3r, 5p + 8q + 5r.
- Вправа 2.8
-
\[
f^*(a_{n-1}, a_{n-2}) = f(a_{n-1}, a_{n-2}) - f(0,0)
\]
Маємо, що $f^*$ однорідна. Нехай
\begin{align*}
u_n &= f^*(u_{n-1}, u_{n-2}),\quad \text{для}\ n > 1, u_0 = 1, u_1 = 0,\\
v_n &= f^*(v_{n-1}, v_{n-2}),\quad \text{для}\ n > 1, v_0 = 0, v_1 = 1.
\end{align*}
Тоді
\[
a_n = a_0 u_n + a_1 v_n + f(0,0)\operatorname{Fib}(n-2).
\]
- Вправа 2.9
-
\[
a_n = \frac{n}{n+2}a_{n-1} = \prod_{k=1}^n \frac{k}{k+2} = \frac{1\cdot 2\cdot \cdots n}{3\cdot 4 \cdots (n+2)} = \frac{1\cdot 2}{(n+1)(n+2)}.
\]
- Вправа 2.10
\[
a_n = 1 + \underbrace{(-1) + 2}_1 + \underbrace{(-3) + 4}_1 \cdots,
\]
\[
a_n=
\begin{cases}
1 + \frac{n}{2} & n\ \text{парне}\\
1 - \frac{n}{2} & n\ \text{непарне}
\end{cases}
\]
-
- Вправа 2.11
\begin{align*}
n(n-1)a_n &= (n-1)(n-2)a_{n-1} + 2(n-1)\\
(n-1)(n-2)a_{n-1} &= (n-2)(n-3)a_{n-4} + 2(n-3)\\
\dots&\\
2\cdot 1\cdot a_2 &= 0\cdot(-1)\cdot 1 + 2\cdot(n-(n-2)-1)
\end{align*}
Тепер складемо всі рівності.
\[
n(n-1)a_n = 2\sum_{k=1}^{n-1}k = n(n-1)
\]
Отримуємо:
\[
a_n = 1
\]
-
- Вправа 2.12
\begin{align*}
2^{-n}a_n &= 2^{-(n-1)}a_{n-1} + 2^{-n}\\
\dots &\\
2^{-2}a_2 &= 2^{-1}\cdot 1 + 2^{-2}\\
\end{align*}
Тепер складемо всі рівності.
\[
2^{-n}a_n = 2^{-1}\cdot 1 + \sum_{k=2}^{n}2^{-k}
\]
Отримуємо:
\[
a_n = 2^{n-1} + \sum_{k=2}^n2^{n-k} = 2^{n-1} + \sum_{k=0}^{n-2}2^k = 2^n - 1.
\]
-
- Вправа 2.13
Тут нам треба звернути увагу на те, що на відміну від теореми 2.1, нулю дорівнює не $a_1$, а $a_0$. Тому сума починається з $j = 0$:
\begin{align*}
a_n &= 1 + \sum_{j=0}^{n-1}\frac{j+1}{j+2}\cdots\frac{n}{n+1}\\
&= 1 + \sum_{j=0}^{n-1}\frac{j+1}{n+1} = 1 + \frac{1}{n+1}\sum_{j=0}^{n-1} (j+1)\\
&= \frac{1}{n+1}\sum_{j=1}^{n+1}j = \frac{n+2}{2}.
\end{align*}
-
- Вправа 2.14
Тут сума починається з $t+1$, також присутній член $a_t$, бо не сказано, що він дорівнює нулю.
\begin{equation}
a_n = y_n + \sum_{j=t+1}^{n-1} y_{j} x_{j+1} \dots x_n + a_tx_{t+1}\dots x_n.\label{eq:rr_at}
\end{equation}
-
- Вправа 2.15
\begin{align*}
a_n &= 2 \sum_{j=1}^{n-1} \frac{j+2}{j+1} \dots \frac{n+1}{n} + 2\\
&= 2 \sum_{j=1}^{n-1}\frac{n+1}{j+1} + 2\\
&= 2(n+1)\left(\sum_{j=1}^{n-1}\frac{1}{j+1}+\frac{1}{n+1}\right)\\
&= 2(n+1)(H_{n+1}-1).
\end{align*}
Під час перевірки можна скористатись тим, що $nH_n - n = \sum_{k=1}^{n-1}H_k$.
\begin{align*}
2n\sum_{k=1}^nH_k &= 2(n+1)\sum_{k=1}^{n-1}H_k + 2n\\
nH_n &= \sum_{k=1}^{n-1}H_k + n
\end{align*}
-
- Вправа 2.16
Скориставшись теоремою 2.1:
\begin{align*}
a_n = 12 H_n + 12 \sum_{j=5}^{n-1} H_j \frac{(j-3)(j-2)(j-1)j}{n(n-1)(n-2)(n-3)},
\end{align*}
або ми можемо використати сумувальний множник $(n-1)(n-2)(n-3)$:
\begin{align*}
n(n-1)(n-2)(n-3)a_n &= (n-1)(n-2)(n-3)(n-4)a_{n-1}\\
&\phantom{=}+ 12 n(n-1)(n-2)(n-3) H_n,\\
(5\cdot 4\cdot 3\cdot 2)a_5 &= 12 (5\cdot 4\cdot 3\cdot 2) H_5.
\end{align*}
Сумуючи отримуємо той самий вислід.
-
- Вправа 2.17
-
Зауважимо, що кожен 2-вузол містить одну вершину, а кожен 3-вузол містить дві вершини, тобто розпадається на два 2-вузли.
\begin{align*}
A_N &= A_{N-1}\left(\frac{N-6}{N}\right) +2 \\
&= 2 + 2 \sum_{j=1}^{N-1}\left(\frac{j-5}{j+1}\right)\dots\left(\frac{N-7}{N-1}\right)\\
\end{align*}
Тут і у попередній вправі $x_n$ дуже схожі. І виконуючи теорему 2.1 нам може захотітись дати таку відповідь:
\[
A_N = 2 + 2 \sum_{j=1}^{N-1} \frac{(j-5)(j-4)(j-3)(j-2)(j-1)j}{N(N-1)(N-2)(N-3)(N-4)(N-5)},
\]
але це не правильно, бо ми не можемо ділити на нуль. Ми мусимо використати \eqref{eq:rr_at}. Отже, відповіддю буде
\begin{align*}
A_N &= 2 + 2 \sum_{j=6}^{N-1} \frac{(j-5)(j-4)(j-3)(j-2)(j-1)j}{N(N-1)(N-2)(N-3)(N-4)(N-5)}\\
&\phantom{=} + A_5\frac{0\cdot1\cdot2\cdot3\cdot4\cdot5}{N(N-1)(N-2)(N-3)(N-4)(N-5)},\quad \text{для }\ N > 5.
\end{align*}
Нам навіть не потрібно вручну обчислювати $A_5$, бо його потрібно множити на $0$.
Щоб краще уявити собі кількість 2-вузлів і перевірити формулу, можна запустити таку програму:
float tree23(int n) {
if (n == 0) return 0;
float prev = tree23(n - 1);
return prev - 2 * prev / n + 2 * (1 - 2 * prev / n);
}
float tree23_sum(int n) {
float sum = 0.;
for (int j = 6; j < n; ++j) {
float num = 1.f, denom = 1.f;
for (int k = 0; k < 6; ++k) {
num *= j - k;
denom *= n - k;
}
sum += num / denom;
}
return 2 + 2 * sum;
}
int main() {
for (int i = 6; i < 30; ++i) {
cout << setw(6) << setprecision(3) << fixed << tree23(i) << " " << tree23_sum(i) << endl;
}
return 0;
}
2.000 2.000
2.286 2.286
2.571 2.571
2.857 2.857
3.143 3.143
3.429 3.429
3.714 3.714
4.000 4.000
4.286 4.286
4.571 4.571
4.857 4.857
5.143 5.143
5.429 5.429
5.714 5.714
6.000 6.000
6.286 6.286
6.571 6.571
6.857 6.857
7.143 7.143
7.429 7.429
7.714 7.714
8.000 8.000
8.286 8.286
8.571 8.571
- Вправа 2.18
\begin{align*}
a_1 &= \frac{1 + 0\cdot a_0}{1+1\cdot a_0} = \frac{\operatorname{Fib}_1 + \operatorname{Fib}_0\cdot a_0}{\operatorname{Fib}_2 + \operatorname{Fib}_1\cdot a_0}\\
a_2 &= \frac{1 + 1\cdot a_0}{2+1\cdot a_0} = \frac{\operatorname{Fib}_2 + \operatorname{Fib}_1\cdot a_0}{\operatorname{Fib}_3 + \operatorname{Fib}_2\cdot a_0}\\
\dots&\\
a_n &= \frac{\operatorname{Fib}_n + \operatorname{Fib}_{n-1}\cdot a_0}{\operatorname{Fib}_{n+1} + \operatorname{Fib}_n\cdot a_0}\\
\end{align*}
Зі збільшенням $n$ перші доданки починають домінувати і ми отримуємо $\frac{\operatorname{Fib}_{n}}{\operatorname{Fib}_{n+1}}$, тоді як ми знаємо, що $\lim_{n\to \infty}\frac{\operatorname{Fib}_{n+1}}{\operatorname{Fib}_{n}} = \varphi$ - золотий перетин, а $\frac{1}{\varphi}$ і є потрібним результатом, з яким $\lim_{n\to \infty} b_n = 0$.
-
- Вправа 2.19
-
|
На рисунку праворуч показани графіки функцій $ y = \cos(x)$ і $x = \cos(y)$ або інакше $y = \arccos(x)$. Точка перетину має абсцису $0.73908\dots$.
|
|
- Вправа 2.20
-
Щоб зрозуміти чому формула працює можна розглянути такий її варіант:
$$2a_na_{n-1} = a_{n-1}^2+b$$
Якщо $b$ від'ємне, то нема причин очікуватись збіжність $a_n$ до $b$.
- Вправа 2.21
-
-
Спершу доведемо, що $a_n \in \Theta(1/n)$.
\begin{align*}
\frac{1}{a_n} &= \frac{1}{a_{n-1}}\frac{1}{1-a_{n-1}}&\\
\frac{1}{a_n} &< \frac{1}{a_{n-1}}\frac{n-1}{n-2}&\text{використали}\ a_n < \frac{1}{n}\\
a_n &> \frac{1}{n-1}a_3&\text{де}\ a_3 = 39/256.
\end{align*}
Отже, для достатньо великих $n$, $a_n > \frac{1}{n-1}$.
-
Тепер оцінимо $c$:
float a = 0.5f;
for (int i = 1; i < 1000; ++i) {
a = a * (1 - a);
cout << setw(15) << a << " " << a * i << endl;
}
...
0.000996334 0.991353
0.000995342 0.99136
0.000994351 0.991368
0.000993362 0.991376
0.000992376 0.991383
Отже, схоже що $c$ дорівнює $1$.
-
З пункту 1 і з книги ми знаємо, що
$$\frac{1}{n-1} < a_n < \frac{1}{n}$$
отже $na_n \to 1$.
- Вправа 2.22
-
-
На початку $\sin(x)$ зростає повільніше ніж $x$, тобто $x > \sin(x)$ окрім як в $0$. Отже послідовність $a_n$ обмежена спадна функція, тобто вона має границю. $\sin(x)$ - неперервна, отже ця границя в стаціонарній точці, єдина така точка в $[0,1]$ це $0$.
-
Тепер доведемо, що $a_n = O(1/\sqrt{n})$.
- Вправа 2.23
-
Розглянемо
$$a_n = \alpha + \varepsilon_{n} = f(a_{n-1}) = f(\alpha + \varepsilon_{n-1}).$$
Використаємо розклад в ряд Тейлора:
$$f(\alpha + \varepsilon_{n-1}) = f(\alpha) + f'(\alpha) * \varepsilon_{n-1} + f''(\alpha) * \varepsilon_{n-1} / 2!.$$
Зауважимо, що $f(\alpha) = \alpha$.
\begin{equation}
\varepsilon_{n} = f'(\alpha) * \varepsilon_{n-1} + f''(\alpha) * \varepsilon_{n-1} / 2!\label{eq:cnvrg_rate_drv}
\end{equation}
Отже, якщо $f'(\alpha) > 1$, то ряд розбігається.
- Вправа 2.24
-
Використовуючи \eqref{eq:cnvrg_rate_drv} маємо квадратну збіжність якщо $f'(\alpha)$ рівне $0$ з коефіцієнтом $f''(\alpha)/2$. Аналогічно можна отримати коефіцієнти для $f'(\alpha) \ne 0$.
- Вправа 2.25
-
Для того, щоб збагнути як утворити необхідне рекурентне відношення розглянемо таке рекурентне відношення:
\begin{equation}
a_n - 3*a_{n-1} = 4*(a_{n-1} - 3*a_{n-2}),\quad a_0 = 0, a_1 = 1.\label{eq:rr_25_43}
\end{equation}
Якщо пройти рекурсивно до базового випадку, маємо:
\begin{align*}
a_n - 3 a_{n-1} &= 4^{n-1}\\
3^1(a_{n-1} - 3 a_{n-2}) &= 3^1 4^{n-2}\\
\dots &\\
3^i(a_{n-i} - 3 a_{n-i-1}) &= 3^i 4^{n-i-1}\\
\dots &\\
3^{n-1}(a_1 - 3 a_0) &= 3^{n-1}
\end{align*}
Складаємо і скорочуємо:
\begin{align*}
a_n = \sum_{i=1}^n 4^{n-i}3^{i-1}
\end{align*}
Зауважимо, що $4^n = 1\dot 4^{n-1} + 3\cdot 4^{n-1}$ або ж $3^{n-1}\dot 4^0 + 3^n\cdot 4^0 = 4\cdot 3^n$. Застосовуючи останню формулу маємо для $n=5$:
$$
\underbrace{4^4\cdot 3^0 +
\underbrace{4^3\cdot3 +
\underbrace{4^2\cdot3^2+
\underbrace{4\cdot3^3 +
\underbrace{3^4\cdot 4^0 + 3^5\cdot 4^0
}_{3^4\cdot 4}
}_{3^3\cdot 4^2}
}_{3^2\cdot 4^3}
}_{3^1\cdot 4^4}
}_{4^5}
$$
Зверніть увагу, що тут ми додали $3^5$, отже формула така:
$$\sum_{i=1}^n 4^{n-i}3^{i-1} = 4^n - 3^n.$$
Тобто розв'язок до \refeq{eq:rr_25_43} такий $a_n = 4^n - 3^n$. Гм.. це маже те, що нам треба! А ось і наша відповідь:
$$a_n - 3*a_{n-1} = 4*(a_{n-1} - 3*a_{n-2})+2^{n-1}.$$
long a(int n) {
switch (n) {
case 0: return 1;
case 1: return 3;
default: return powl(4, n) - powl(3, n) + powl(2,n);
}
}
for (int n = 2; n < 25; ++n) {
long lhs = a(n) - 3 * a(n - 1);
long rhs = 4 * (a(n - 1) - 3 * a(n - 2)) + powl(2,n-1);
cout << setw(2) << n << ": " << setw(10) << lhs << " " << rhs << endl;
}
2: 2 2
3: 12 12
4: 56 56
5: 240 240
6: 992 992
7: 4032 4032
...
- Вправа 2.26
-
-
Ввести $b_n = a_n - a_{n-1}$, це дасть нам однорідне рекурентне відношення.
-
Розписати в стовпчик усі $a_i - a_{i-1}$ і скласти, завдяки телескопуванню, ми зможемо отримати формулу для $a_n$, спрощення цієї формули може бути досить складним.
- Вправа 2.27
-
Характеристичний многочлен такий:
$$\beta^2 - 5\beta + 6 = 0.$$
Коренями є $2, 3$. Значить маємо розв'язки у вигляді $c_12^n + c_23^n$. Звідси бачимо, що для розв'язку $2^n$ $c_1 = 1, c_2 = 0$, а розв'язок $2^n - 1$ отримати не можливо.
- Вправа 2.28
-
Корені $2, -i, i$.
-
$a_0 = a_1 = a_2 = 0$.
-
$a_0 = a_1 = a_2 = 1$.
-
$a_0 = i, a_1 = -1, a_2 = i$.
- Вправа 2.29
-
Коренями є $1+\sqrt{5}, 1-\sqrt{5}$. Відповідь $\frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{2\sqrt{5}}$.
- Вправа 2.30
-
Перепишемо рекурентне відношення у вигляді
$$a_n - a_{n-1} = a_{n-1} - a_{n-2}.$$
Ми бачимо, що зі зростанням $n$ на одиницю $a$ зростає на сталу. Звідси нам легко знайти відповіді.
-
$a_n = n$.
-
$a_n = 1$.
- Вправа 2.31
-
Тут корені це $\frac{1\pm i\sqrt{3}}{2}$. Отже, маємо два рівняння:
\begin{cases}
c_1 + c_2 &= 0\\
c_1\frac{1 + i\sqrt{3}}{2} + c_2\frac{1 - i\sqrt{3}}{2} &= 1
\end{cases}
Що дає $c_1 = -c_2 = \frac{1}{i\sqrt{3}}$. І, власне, розв'язок:
$$a_n = \frac{1}{i\sqrt{3}}\left(\frac{1 + i\sqrt{3}}{2}\right)^n -\frac{1}{i\sqrt{3}}\left(\frac{1 - i\sqrt{3}}{2}\right)^n$$
- Вправа 2.32
-
Корені тут $\frac{1}{2}, \frac{1\pm\sqrt{3}}{2}$.
\begin{cases}
c_1+c_2+c_3 &= 0\\
c_1\frac{1}{2}+c_2 \frac{1+\sqrt{3}}{2}+c_3 \frac{1-\sqrt{3}}{2} &= 1\\
c_1\left(\frac{1}{2}\right)^2+c_2 \left(\frac{1+\sqrt{3}}{2}\right)^2+c_3 \left(\frac{1-\sqrt{3}}{2}\right)^2 &= 2
\end{cases}
- Вправа 2.33
-
$$a_n = 4(a_{n-2}-a_{n-4}).$$
При $a_0 = 1, a_1 = -1, a_2 = 2, a_3 = -2$. Для парних маємо $1,2,4,8,\dots$ і для непарних те саме тільки з мінусом.
- Вправа 2.34
-
>> p = [1 -1 -1 -1];
>> r = roots(p)
r =
1.83929 + 0.00000i
-0.41964 + 0.60629i
-0.41964 - 0.60629i
>> A = [r.^0'; r.^1'; r.^2'];
>> b = [0 0 1]';
>> c = A\b
c =
0.182804 + 0.000000i
-0.091402 - 0.340547i
-0.091402 + 0.340547i
>> F20_exact = r.^19' * c
F20_exact = 1.9513e+004 + 6.5683e-013i
>> F20_approx = r(1)^19' * c(1)
F20_approx = 1.9513e+004 + 6.5683e-013i
- Вправа 2.35
-
Домножити обидва боки на $(n-2)!$. Маємо Фібоначчі:
$$n!a_n = (n-1)!a_{n-1} + (n-2)!a_{n-2}.$$
Отже, $a_n = F_n / n!$.
- Вправа 2.36
-
Входження $t_i$ означає відсутність $a_i$ і $a_{i+1}$. Всі одночлени - унікальні.
- Вправа 2.37
-
Характеристичний многочлен для послідовності $b_n$ такий: $x^2 - \frac{1}{2}x - \frac{1}{2} = 0$. Корені - $1, -\frac{1}{2}$.
\begin{cases}
c_1+c_2 &= 0\\
c_1 + c_2\left(-\frac{1}{2}\right) & = 1
\end{cases}
Звідси, $c_1 = -c_2 = \frac{2}{3}$. І відповідь
$$b_n = \frac{2}{3} - \frac{2}{3}\left(-\frac{1}{2}\right)^n.$$
$$a_n = 2^{\frac{2}{3} - \frac{2}{3}\left(-\frac{1}{2}\right)^n}.$$
- Вправа 2.38
-
Введемо заміну змінних $b_n = a_n^2$. Маємо:
$$b_n = b_{n-1} + 1.$$
Це відношення має розв'язок $b_n = n$. Відповідно, $a_n = \sqrt{n}$.
- Вправа 2.39
-
Для отримання формули в для $a_0 = 3, a_0 = 4$ необхідно підставити конкретні значення в формулу наведену в книзі. У випадку коли $a_0 = \frac{3}{2}$ послідовність "хаотично" рухається в $[-2, 2 ]$.
- Вправа 2.40
-
Для великих $\epsilon$:
\begin{align*}
a_n &\approx \left(\frac{1}{2}(2+\epsilon + \sqrt{(2+\epsilon)^2 - 4}\right)^{2^n}\\
&= \left(\frac{1}{2}(2+\epsilon+\sqrt{4+4\epsilon+\epsilon^2 -4})\right)^{2^n}&\quad\text{в підкорінневому виразі домінує}\ \epsilon^2\\
&\approx \left(1 + \epsilon\right)^{2^n}\\
&\approx \epsilon^{2^n}.
\end{align*}
- Вправа 2.41
-
Якщо $b_n = f\cdot a_n + g$, тоді $a_n = \frac{b_n-g}{f}$.
\begin{align*}
\frac{b_n - g}{f} &= \alpha\left(\frac{b_{n-1} - g}{f}\right)^2 + \beta\frac{b_{n-1} - g}{f} + \gamma\\
b_n &= \frac{\alpha}{f}(b_{n-1} - 2b_{n-1}g + g^2)+\beta b_{n-1}-\beta g + \gamma f + g\\
b_n &= \underbrace{\frac{\alpha}{f}}_{=1}b_{n-1}^2 - \underbrace{\left(\frac{2\alpha g}{f}-\beta\right)}_{=0}b_{n-1} + \underbrace{\frac{\alpha g^2}{f} - \beta g + \gamma f + g}_{=-2}
\end{align*}
З цього ми миожемо зробити такі висновки: $f = \alpha$, $g = \frac{\beta}{2}$. А те, що $\frac{\alpha g^2}{f} - \beta g + \gamma f + g = -2$ дозволяє нам обрати значення для $\alpha, \beta, \gamma$, ми маємо два ступені свободи тут.
Наприклад, $\beta = 2, \alpha = 1, \gamma = -2$.
$$a_n = a_{n-1}^2 + 2 a_{n-1} - 2$$
Отже, $f = 1$, $g = 1$ і $b_n = a_b + 1$. Перевіримо:
\begin{align*}
a_n + 1 &= (a_{n-1} + 1)^2 - 2\\
& = a_{n-1}^2 + 2 a_{n-1} + 1 - 2
\end{align*}
Що дає
$$a_n = a_{n-1}^2 + 2 a_{n-1} -2.$$
- Вправа 2.42
-
\begin{align*}
a_n &= 2 a_{n-1} \sqrt{1-a_{n-1}^2}&\quad n>0, a_0=\frac{1}{2}\\
a_n^2 &= 4 a_{n-1}^2 (1-a_{n-1}^2)\\
b_n &= 4b_{n-1}-4b_{n-1}^2&\quad b_n=a_n^2
\end{align*}
Тут ми можемо використати результат попередньої вправи з $\alpha = -4$, $\beta = -4$, $\gamma = 0$. Тоді $c_n = -4b_n+2$. Маємо
$$c_n = c_{n-1}^2 - 2.$$
А це вже алгоритм розподілення регістрів з книги.
- Вправа 2.43
-
Ми можемо переписати нашу рекуренцію так:
$$a_n = \underbrace{\frac{\alpha a_{n-1}}{\gamma a_{n-1} + \delta}}_{a'_{n}} + \underbrace{\frac{\beta}{\gamma a_{n-1} + \delta}}_{a''_{n}}.$$
Тепер ми можемо працювати з двома рекуренціями і скласти їх результати.
\begin{align*}
a'_n &= \frac{\alpha a'_{n-1}}{\gamma a'_{n-1} + \delta}\\
\frac{1}{a'_n} &= \frac{\gamma}{\alpha} + \frac{\delta}{\alpha}\frac{1}{a'_{n-1}}&\quad b'_n = \frac{1}{a'_n}\\
b'_n &= \frac{\gamma}{\alpha} + \frac{\delta}{\alpha}b'_{n-1}\\
\end{align*}
Тепер подібно до теореми 2.1:
$$b'_n = \frac{\gamma}{\alpha}\sum_{i=0}^{n-1}\left(\frac{\delta}{\alpha}\right)^i + \left(\frac{\delta}{\alpha}\right)^nb'_0.$$
Друга рекуренція майже як в прикладі з книги:
\begin{align*}
a''_n &= \frac{\beta}{\gamma a''_{n-1} + \delta}&\quad a''_n = \frac{b''_{n-1}}{b''_n}\\
b''_n &= \frac{\delta}{\beta}b''_{n-1} + \frac{\gamma}{\beta}b''_{n-2}\\
\end{align*}
Тут ми знайдемо два корені і нам буде потрібно вибрати значення коефіцієнтів залежно початкових умов. Тобто, початкова умова $a_0 = a'_0 + a''_0 = 1$ має виконуватись.
- Вправа 2.44
-
Розпишемо перші члени послідовності $(a_n)$:
\begin{align*}
a_0 &= 1\\
a_1 &= \frac{1}{s_1+t_1}\\
a_2 &= \frac{s_1+t_1}{s_2s_1+s_2t_1 + t_2}\\
a_3 &= \frac{s_2s_1+s_2t_1 + t_2}{s_3s_2s_1+s_3s_2t_1 + s_3t_2 + t3s_1 + t_3t_1}\\
a_4 &= \frac{s_3s_2s_1+s_3s_2t_1 + s_3t_2 + t_3s_1 + t_3t_1}{s_4s_3s_2s_1+s_4s_3s_2t_1 + s_4s_3t_2 + s_3t_2s_1 + s_3t_2t_1 + t_4s_2s_1+t_4s_2t_1 + t_4t_2}\\
\end{align*}
Тут ми вже бачимо взірець за яким можна будувати наступні члени. Ми можемо записати послідовність трошки інакше:
$$a_n = \frac{s_{n-1}\operatorname{den}{a_{n-2}} + t_{n-1}\operatorname{nom}{a_{n-2}}}{s_{n}\operatorname{den}{a_{n-1}} + t_{n}\operatorname{nom}{a_{n-1}}}$$
Зверніть увагу на послідовність опрацьовану в вправі 2.36, вона дуже подібна.
Якщо $a_n = \frac{b_{n}}{b_{n+1}}$, то
$$b_n = s_{n-1}b_{n-1}+t_{n-1}b_{n-2},\quad n>1,\ b_0 = b_1 = 1.$$
- Вправа 2.45
-
Найперше ми маємо знайти форму $a_n$, яка дасть нам входження $n^3$ в $a_n - \left(2\sum_{j=0}^{n-1}\right)/n$. Для цього ми можемо вибрати $n(n-1)(n-2)$.
\begin{align*}
\sum_{k=0}^n k(k-1)(k-2) & = \sum_{k=0}^n (k^2 - 3k^2 + 2k)\\
&= \frac{n^2(n+1)^2}{4} - \frac{n(n+1)(2n+1)}{2} + n(n+1)\\
&= \frac{1}{4}(n^4 - 2n^3 - n^2 + 2n).
\end{align*}
Перевіримо:
$$a_3 = (3\cdot 2 \cdot 1) = 6 = \frac{1}{4}(81 - 54 - 9 + 6).\quad\text{збіг!}$$
Отже,
\begin{align*}
a_n - \left(2\sum_{j=0}^{n-1}\right)/n & = n(n-1)(n-2)\\
&\phantom{=}- \frac{1}{2}\big((n-1)^4 - 2(n-1)^3 - (n-1)^2 + 2(n-1)\big)/n
\end{align*}
Тепер маючи компонент з $n^3$ ми можемо за допомогою нескладної, але нудної алгебри зкомпонувати його з уже відомими розв'язками, щоб отримати $f(n) = n^3$.
- Вправа 2.46
-
Розв'яжіть рекурентне відношення для швидкого сортування медіани трьох використовуючи репертуарний метод.
$$c_n = n+1+\sum_{k=1}^n\frac{(n-k)(k-1)}{\binom{n}{3}}(c_{k-1} + c_{n-k}),\quad n>3.$$
Перепишемо:
\begin{align*}
c_n &= n+1+\frac{2}{\binom{n}{3}}\sum_{k=0}^{n-1}(n-(k+1))((k+1)-1))c_{k}\\
&=n+1+\frac{2}{\binom{n}{3}}\sum_{k=0}^{n-1}(nk- k^2 - k)c_{k}
\end{align*}
Заповнимо репертуарну таблицю:
\begin{align*}
&\phantom{=\ }1 - \frac{2}{\binom{n}{3}}\sum_{k=0}^{n-1}(nk - k^2 - k)\\
&= 1 - \frac{2}{\binom{n}{3}}\left(\frac{n^2(n-1)}{2} - \frac{(n-1)n(2n-1)}{6} + \frac{n(n-1)}{2}\right)\\
&= 1 - 2\frac{3\cdot 2}{n(n-1)(n-2)}\left(\frac{1}{6}(n^3-3n^2+2n)\right)\\
&= -1.
\end{align*}
\begin{align*}
&\phantom{=\ }n - \frac{2}{\binom{n}{3}}\sum_{k=0}^{n-1}(nk^2 - k^3 - k^2)\\
&= n - \frac{2}{\binom{n}{3}}\left((n-1)\frac{(n-1)n(2n-1)}{6} - \frac{(n-1)^2n^2}{4}\right)\\
&= n - 2\frac{3\cdot 2}{n(n-1)(n-2)}\frac{1}{12}n(n-1)^2(n-2)\\
&= 1.
\end{align*}
- Для $c_n = (n-1)^{\underline t}$:
\begin{align*}
&\phantom{=\ }(n-1)^{\underline t} - \frac{2}{\binom{2}{3}}\sum_{1\lt k\lt n}(k-1)(n-k)(k-2)^{\underline t}\\
&= (n-1)^{\underline t} - \frac{2}{\binom{n}{3}}\sum_{1\lt k\lt n}(n-k)(k-1)^{\underline {t+1}}\\
&= (n-1)^{\underline t} - \frac{2(t+1)!}{\binom{n}{3}}\sum_{1\lt k\lt n}(n-k)\binom{k-1}{t+1}\\
&= (n-1)^{\underline t} - \frac{2(t+1)!}{\binom{n}{3}}\sum_{1\lt k\lt n}\binom{n}{t+3}\\
&= (n-1)^{\underline t} - \frac{2(t+1)!}{\binom{n}{3}}\binom{n}{t+3}\\
&= (n-1)^{\underline t} - \frac{12}{(t+2)(t+3)}(n-3)^{\underline{t}}\\
\end{align*}
Бррр... Лінійний час видобути не так просто. І не дивно, ми ж очікуємо, що ця рекурсія виконується за $n \lg n$.
- Для $c_n = \sum_{k=1}^n H_n$:
\begin{align*}
&\phantom{=\ }n - \frac{2}{\binom{n}{3}}\sum_{k=0}^{n-1}((n-1)k - k^2)\sum_{i=1}^k H_i\\
\end{align*}
Не завершено.
- Вправа 2.47
-
Ми бачимо, що
$$\frac{2}{n+1} < a_n < \frac{2}{n}.$$
Тепер підставимо значення для $a_{n-1}$ в рекуренцію:
\begin{align*}
\frac{2}{n+\frac{2}{n}} &< a_n < \frac{2}{n + \frac{2}{n-1}}\\
\frac{2n}{n^2+2} &< a_n < \frac{2(n-1)}{n^2 - n + 2}\\
\end{align*}
Але $\frac{2}{n+1} < \frac{2n}{n^2+2}$ і $\frac{2(n-1)}{n^2 - n + 2} < \frac{2}{n}$, тобто завдяки бутстрепу вдалось звузити діапазон можливих начень $a_n$.
Вправи з 48 і далі нерозв'язані.
