3.11: Вправи

1. База даних використовує ідентифікатори записів, які є буквено-цифровими рядками, в яких 10 десяткових знаків і 26 великих букв є дійсними символами. Критерії, що визначають дійсний ідентифікатор запису, є рекурсивними. Дійсний ідентифікатор запису довжини$n \geq 2$ може бути побудований наступними способами:

• починаючи з будь-якої великої$D$ літери, крім якої слід будь-який дійсний ідентифікатор запису довжини$n−1$;
• починаючи з$1C, 2K$, або$7J$ за яким слідує будь-який дійсний ідентифікатор запису довжини$n−2$;
• починаючи з$D$ і за яким слідує будь-який рядок$n-1$ десяткових цифр;

$r(n)$Дозвольте позначити кількість дійсних ідентифікаторів запису довжини$n$. Беремо$r(0)=1$ і відзначимо, що$r(1)=26$. Знайдіть рекурсію для$r(n)$$n \geq 2$ when і використовуйте її для обчислення$r(5)$.

2. Розглянемо$1 \times n$ шахову дошку. Квадрати шахової дошки повинні бути пофарбовані в білий і золотий колір, але жодні два послідовних квадрата не можуть бути пофарбовані в білий колір. Давайте$p(n)$ позначимо кількість способів фарбування шахової дошки при дотриманні цього правила. Знайти рекурсивну формулу для$p(n)$ допустимого для$n \geq 3$.

3. Дайте рекурсію для$g(n)$ кількості потрійних рядків довжини$n$, які не містять 102 як підрядок.

4. $2 \times n$Шахова дошка повинна бути облицьована плиткою з використанням двох видів плитки. Перша плитка -$1 \times 1$ квадратна плитка. Друга плитка називається$L$ -tile і формується шляхом видалення верхнього правого$1 \times 1$ квадрата з$2 \times 2$ плитки. The$L$ -tiles може бути використаний будь-яким з чотирьох способів їх можна обертати. (Тобто «відсутній квадрат» може перебувати в будь-якому з чотирьох положень.) Нехай$t(n)$ позначають кількість плиток$2 \times n$ шахової дошки за допомогою$1 \times 1$ плитки і$L$ -плитки. Знайдіть рекурсивну формулу для$t(n)$ і використовуйте її для визначення$t(7)$.

5. $S$Дозволяти набір рядків на алфавіті$\{0,1,2,3\}$, які не містять 12 або 20 як підрядок. Дайте рекурсію для$h(n)$ кількості$S$ рядків довжиною$n$.

Підказка

Перевірте рекурсію вручну обчислюючи$h(1), h(2), h(3)$, і$h(4)$.

6. Знайти$d=gcd(5544,910)$, а також цілі числа$a$ і$b$ такі, що$5544a + 910b = d$.

7. Знайти$gcd(827,249)$, а також цілі числа$a$ і$b$ такі, що$827a+249b=6$.

8. Нехай$a,b,m$, і$n$ бути цілими числами і припустимо, що$am+bn=36$. Про що можна сказати$gcd(m,n)$?

9. (Складна задача) Для кожної формули дайте як доказ, використовуючи принцип математичної індукції, так і комбінаторне доказ. Один з двох буде легше, а інший буде складнішим.

а)$1^2+2^2+3^2+ \cdot \cdot \cdot + n^2 = \dfrac{n(n+1)(2n+1)}{6}$

б)$\dbinom{n}{0}2^0 + \dbinom{n}{1}2^1 + \dbinom{n}{2}2^2 + \cdot \cdot \cdot + \dbinom{n}{n}2^n = 3^n$

10. Показати, що для всіх цілих чисел$n \geq 4$,$2^n < n!$.

11. Показати, що для всіх натуральних чисел$n$,

$\displaystyle \sum_{i=0}^n 2^i = 2^{n+1} - 1$.

12. Показати, що для всіх натуральних чисел$n, 7^n- 4^n$ ділиться на 3.

13. Показати, що для всіх натуральних чисел$n,9^n-5^n$ ділиться на 4.

14. Виходить, що якщо$a$ і$b$ є додатними цілими числами з$a > b+1$, то є додатне число$M > 1$$a^n-b^n$ таке, яке ділиться на$M$ для всіх натуральних чисел$n$. Визначити$M$ через$a$ і$b$ і довести, що це дільник$a^n-b^n$ для всіх натуральних чисел$n$.

15. Використовуйте математичну індукцію, щоб довести, що для всіх цілих$n \geq 1$ чисел

$n^3+(n+1)^3 + (n+2)^3$

ділиться на 9.

16. Наведіть доказ шляхом індукції біноміальної теореми (теорема 2.30). Як ви думаєте, це порівнюється з комбінаторним аргументом, наведеним у главі 2?

17. Розглянемо рекурсію, задану$f(n)=2f(n−1)−f(n−2)+6$ for$n \geq 2$ з$f(0)=2$ і$f(1)=4$. Використовуйте математичну індукцію, щоб довести, що$f(n)=3n^2−n+2$ для всіх цілих чисел$n \geq 0$.

18. Розглянемо рекурсію, задану$f(n)=f(n−1)+f(n−2)$ for$n \geq 3$ with$f(1)=f(2)=1$. Показати,$f(n)$ що ділиться на 3, якщо і тільки якщо$n$ ділиться на 4.

19. Припустимо, що$x \in \mathbb{R}$ і$x > −1$. Доведіть, що для всіх цілих чисел$n \geq 0$,$(1+x)^n \geq 1 + nx$.

20. Показати, що існує позитивна константа,$c$ так що будь-який алгоритм, який сортує послідовність$n$ натуральних чисел, повинен, у гіршому випадку, вжити$cn \log n$ заходів.

Підказка

Існують$n!$ перестановки множини$n$ різних цілих чисел. Кожна операція зменшує кількість можливостей на мультиплікативний дріб, який є не більше$1/2$. Так що якщо є$t$ операції, то$2^t \geq n!$. Тепер шукайте наближення Стірлінга для$n!$ і продовжуйте звідти.