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!\) і продовжуйте звідти.