2.E: Послідовності (вправи)

Template:MathjaxLevin

2.1: Визначення

1

Знайдіть замкнуту формулу для кожної з наступних послідовностей, зв'язавши їх з відомою послідовністю. Припустимо, що перший заданий термін є$a_1\text{.}$

1. $2, 5, 10, 17, 26, \ldots$
2. $0, 2, 5, 9, 14, 20, \ldots$
3. $8, 12, 17, 23, 30,\ldots$
4. $1, 5, 23, 119, 719,\ldots$

Відповідь

1. $a_n = n^2 + 1\text{.}$
2. $a_n = \frac{n(n+1)}{2} - 1\text{.}$
3. $a_n = \frac{(n+2)(n+3)}{2} + 2\text{.}$
4. $a_n = (n+1)! - 1$(де$n! = 1 \cdot 2 \cdot 3 \cdots n$).

2

Для кожної наведеної нижче послідовності знайдіть замкнуту$a_n\text{,}$ формулу для$n$ го члена послідовності (припустимо, що перші члени є$a_0$), зв'язавши її з іншою послідовністю, для якої ви вже знаєте формулу. У кожному конкретному випадку коротко скажіть, як ви отримали свої відповіді.

1. 4, 5, 7, 11, 19, 35,...
2. 0, 3, 8, 15, 24, 35,...
3. 6, 12, 20, 30, 42,...
4. 0, 2, 7, 15, 26, 40, 57,... (Загадкова підказка: їх можна назвати «номерами будинків»)

3

Послідовність Фібоначчі є$0, 1, 1, 2, 3, 5, 8, 13, \ldots$ (де$F_0 = 0$).

1. Дайте рекурсивне визначення послідовності.
2. Випишіть перші кілька членів послідовності часткових сум:$0\text{,}$$0+1\text{,}$$0+1+1\text{,}$...
3. Дайте замкнуту формулу для послідовності часткових сум у терміні$F_n$ (наприклад, можна сказати,$F_0 + F_1 + \cdots + F_n = 3F_{n-1}^2 + n\text{,}$ хоча це точно не правильно).

Відповідь

1. $F_n = F_{n-1} + F_{n-2}$з$F_0 = 0$ і$F_1 = 1\text{.}$
2. $0, 1, 2, 4, 7, 12, 20, \ldots.$
3. $F_0 + F_1 + \cdots + F_n = F_{n+2} - 1.$

4

Розглянемо три послідовності нижче. Для кожного знайдіть рекурсивне визначення. Як пов'язані ці послідовності?

1. $2, 4, 6, 10, 16, 26, 42, \ldots\text{.}$
2. $5, 6, 11, 17, 28, 45, 73, \ldots\text{.}$
3. $0, 0 , 0 , 0 , 0 , 0 , 0 ,\ldots\text{.}$

Відповідь

Усі послідовності мають однакове відношення повторення:$a_n = a_{n-1} + a_{n-2}$ (те саме, що і числа Фібоначчі). Єдина відмінність - початкові умови.

5

Показати, що$a_n = 3\cdot 2^n + 7\cdot 5^n$ це рішення відношення повторення$a_n = 7a_{n-1} - 10a_{n-2}\text{.}$ Якими повинні бути початкові умови, щоб це була замкнута формула для послідовності?

6

Випишіть перші кілька членів послідовності, заданої$a_1 = 3\text{;}$$a_n = 2a_{n-1} + 4\text{.}$ потім знайдіть рекурсивне визначення для послідовності$10, 24, 52, 108, \ldots\text{.}$

7

Випишіть перші кілька членів послідовності, заданої$a_n = n^2 - 3n + 1\text{.}$ Потім знайдіть замкнуту формулу для послідовності (починаючи з$a_1$)$0, 2, 6, 12, 20, \ldots\text{.}$

8

Знайти замкнуту формулу для послідовності з$a_n = 2a_{n-1} - a_{n-2}$ рекурсивним визначенням з$a_1 = 1$ і$a_2 = 2\text{.}$

9

Знайдіть рекурсивне визначення для послідовності із закритою формулою$a_n = 3 + 2n\text{.}$ Бонусні бали, якщо ви можете дати рекурсивне визначення, в якому використовуються два попередні члени та відсутність констант.

2.2: Арифметичні та геометричні послідовності

1

Розглянемо послідовність$5, 9, 13, 17, 21, \ldots$ з$a_1 = 5$

1. Дайте рекурсивне визначення послідовності.
2. Дайте замкнуту формулу для$n$ го члена послідовності.
3. Чи$2013$ є термін у послідовності? Поясніть.
4. Скільки термінів$5, 9, 13, 17, 21, \ldots, 533$ має послідовність?
5. Знайдіть суму:$5 + 9 + 13 + 17 + 21 + \cdots + 533\text{.}$ Покажіть свою роботу.
6. Використовуйте те, що ви знайшли вище$b_n\text{,}$, щоб знайти$n^{th}$ термін$1, 6, 15, 28, 45, \ldots\text{,}$ де$b_0 = 1$

Відповідь

1. $a_n = a_{n-1} + 4$з$a_1 = 5\text{.}$
2. $a_n = 5 + 4(n-1)\text{.}$
3. Так, так як$2013 = 5 + 4(503-1)$ (так$a_{503} = 2013$).
4. 133
5. $\frac{538\cdot 133}{2} = 35777\text{.}$
6. $b_n = 1 + \frac{(4n+6)n}{2}\text{.}$

2

Розглянемо послідовність, з$(a_n)_{n \ge 0}$ якої починається$8, 14, 20, 26, \ldots\text{.}$

1. Який наступний член в послідовності?
2. Знайдіть формулу для$n$ члена цієї послідовності.
3. Знайдіть суму перших 100 членів послідовності:$\sum_{k=0}^{99}a_k\text{.}$

Відповідь

1. $32\text{,}$який є$26+6\text{.}$
2. $a_n = 8 + 6n\text{.}$
3. $30500\text{.}$Ми хочемо$8 + 14 + \cdots + 602\text{.}$ Reverse і додати, щоб отримати 100 сум 610, загалом 61000, що вдвічі більше суми, яку ми шукаємо.

3

Врахуйте суму$4 + 11 + 18 + 25 + \cdots + 249\text{.}$

1. Скільки термінів (домовленості) в сумі?
2. Обчислити суму. Не забудьте показати всі свої роботи.

Відповідь

1. 36.
2. $\frac{253 \cdot 36}{2} = 4554\text{.}$

4

Розглянемо послідовність$1, 7, 13, 19, \ldots, 6n + 7\text{.}$

1. Скільки термінів є в послідовності?
2. Що таке термін від другого до останнього?
3. Знайдіть суму всіх членів у послідовності.

Відповідь

1. $n+2$терміни, оскільки, щоб отримати 1 за допомогою формули,$6n+7$ ми повинні використовувати$n=-1\text{.}$ Таким чином, у нас є$n$ терміни, плюс$n=0$ і$n=-1$ терміни.
2. $6n+1\text{,}$який на 6 менше$6n+7$ (або підключіть$n-1$ для$n$).
3. $\frac{(6n+8)(n+2)}{2}\text{.}$Зворотний і додати. Кожна сума дає константу$6n+8$ і є$n+2$ терміни.

5

Знайти$5 + 7 + 9 + 11+ \cdots + 521\text{.}$

Відповідь

$68117\text{.}$Якщо взяти$a_0 = 5\text{,}$ члени суми - це арифметична послідовність із замкнутою формулою,$a_n = 5+2n\text{.}$ то$521 = a_{258}\text{,}$ для всього 259 членів в сумі. Поверніть і додайте, щоб отримати 259 однакових 526 термінів, що вдвічі перевищує загальну кількість, яку ми шукаємо. $526\cdot 259 = 68117$

6

Знайти$5 + 15 + 45 + \cdots + 5\cdot 3^{20}\text{.}$

Відповідь

$\frac{5-5\cdot 3^{21}}{-2}\text{.}$Нехай сума буде$S\text{,}$ і обчислити$S - 3S = -2S\text{,}$, що викликає терміни, крім$5$ і$-5\cdot 3^{21}$ скасувати. Тоді вирішуйте для$S\text{.}$

7

Знайти$1 - \frac{2}{3} + \frac{4}{9} - \cdots + \frac{2^{30}}{3^{30}}\text{.}$

8

Знайти$x$ і$y$ таке, що$27, x, y, 1$ є частиною арифметичної послідовності. Потім знайти$x$ і$y$ так, щоб послідовність була частиною геометричної послідовності. (Увага:$x$ і не$y$ може бути цілими числами.)

9

Починаючи з будь-якого прямокутника, ми можемо створити новий, більший прямокутник, прикріпивши квадрат до довшої сторони. Наприклад, якщо ми починаємо з$2\times 5$ прямокутника, ми б приклеїли на$5\times 5$ квадрат, утворюючи$5 \times 7$ прямокутник:

1. Створіть послідовність прямокутників, використовуючи це правило, починаючи з$1\times 2$ прямокутника. Потім випишіть послідовність периметрів для прямокутників (перший член послідовності буде дорівнює 6, так як периметр$1\times 2$ прямокутника дорівнює 6 - наступний член буде 10).
2. Повторіть вищевказану частину на цей раз, починаючи з$1 \times 3$ прямокутника.
3. Знайдіть рекурсивні формули для кожної з послідовностей периметрів, знайдених у частинок (a) та (b). Не забудьте також дати початкові умови.
4. Чи є послідовності арифметичними? Геометричний? Якщо ні, чи близькі вони до того, щоб бути будь-яким із них (тобто відмінності чи співвідношення майже постійні)? Поясніть.

10

Розглянемо послідовність$2, 7, 15, 26, 40, 57, \ldots$ (з$a_0 = 2$). Дивлячись на відмінності між термінами, висловіть послідовність як послідовність часткових сум. Потім знайдіть замкнуту формулу для послідовності шляхом обчислення$n$ ї часткової суми.

Відповідь

У нас є$2 = 2\text{,}$$7 = 2+5\text{,}$$15 = 2 + 5 + 8\text{,}$$26 = 2+5+8+11\text{,}$ і так далі. Члені в сумах задаються арифметичною послідовністю$b_n = 2+3n\text{.}$ Іншими словами,$a_n = \sum_{k=0}^n (2+3k)\text{.}$ щоб знайти замкнуту формулу, повертаємо назад і складаємо. Отримуємо$a_n = \frac{(4+3n)(n+1)}{2}$ (у нас$n+1$ там, тому що є$n+1$ терміни в сумі за$a_n$).

11

Якщо зубочисток вистачить, можна зробити велику трикутну сітку. Нижче наведені трикутні сітки розміру 1 і розміру 2. На сітку 1 розміру потрібно 3 зубочистки, сітка розміру 2 вимагає 9 зубочисток.

1. Нехай$t_n$ буде кількість зубочисток, необхідних для виготовлення розмірної$n$ трикутної сітки. Випишіть перші 5 членів послідовності$t_1, t_2, \ldots\text{.}$
2. Знайдіть рекурсивне визначення послідовності. Поясніть, чому ви маєте рацію.
3. Послідовність арифметична або геометрична? Якщо ні, то це послідовність часткових сум арифметичної або геометричної послідовності? Поясніть, чому ваша відповідь правильна.
4. Використовуйте результати з частини (c), щоб знайти замкнуту формулу для послідовності. Покажіть свою роботу.

12

Використовуйте позначення summation ($\sum$$\prod$) або product (), щоб переписати наступне.

1. $2 + 4 + 6 + 8 + \cdots + 2n\text{.}$
2. $1 + 5 + 9 + 13 + \cdots + 425\text{.}$
3. $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{50}\text{.}$
4. $2 \cdot 4 \cdot 6 \cdot \cdots \cdot 2n\text{.}$
5. $(\frac{1}{2})(\frac{2}{3})(\frac{3}{4})\cdots(\frac{100}{101})\text{.}$

Відповідь

1. $\d\sum_{k=1}^n 2k\text{.}$
2. $\d\sum_{k=1}^{107} (1 + 4(k-1))\text{.}$
3. $\d\sum_{k=1}^{50} \frac{1}{k}\text{.}$
4. $\d\prod_{k=1}^n 2k\text{.}$
5. $\d\prod_{k=1}^{100} \frac{k}{k+1}\text{.}$

13

Розгорніть наступні суми та продукти. Тобто випишіть їх довгим шляхом.

1. $\d\sum_{k=1}^{100} (3+4k)\text{.}$
2. $\d\sum_{k=0}^n 2^k\text{.}$
3. $\d\sum_{k=2}^{50}\frac{1}{(k^2 - 1)}\text{.}$
4. $\d\prod_{k=2}^{100}\frac{k^2}{(k^2-1)}\text{.}$
5. $\d\prod_{k=0}^n (2+3k)\text{.}$

Відповідь

1. $\d\sum_{k=1}^{100} (3+4k) = 7 + 11 + 15 + \cdots + 403\text{.}$
2. $\d\sum_{k=0}^n 2^k = 1 + 2 + 4 + 8 + \cdots + 2^n\text{.}$
3. $\d\sum_{k=2}^{50}\frac{1}{(k^2 - 1)} = 1 + \frac{1}{3} + \frac{1}{8} + \frac{1}{15} + \cdots + \frac{1}{2499}\text{.}$
4. $\d\prod_{k=2}^{100}\frac{k^2}{(k^2-1)} = \frac{4}{3}\cdot\frac{9}{8}\cdot\frac{16}{15}\cdots\frac{10000}{9999}\text{.}$
5. $\d\prod_{k=0}^n (2+3k) = (2)(5)(8)(11)(14)\cdots(2+3n)\text{.}$

2.3: Підгонка поліномів

1

Використовуйте поліноміальну підгонку, щоб знайти формулу для$n$ го члена послідовностей$(a_n)_{n \ge 0}$ нижче.

1. 2, 5, 11, 21, 36,...
2. 0, 2, 6, 12, 20,...
3. 1, 2, 4, 8, 15, 26...
4. 3, 6, 12, 22, 37,... Знайшовши тут формулу, порівняйте з частиною (а).

Відповідь

1. Зверніть увагу, що треті відмінності є постійними, тому$a_n = an^3 + bn^2 + cn + d\text{.}$ використовуйте терміни послідовності, щоб вирішити для$a, b, c,$ і$d$ отримати$a_n = \frac{1}{6} (12+11 n+6 n^2+n^3)\text{.}$
2. $a_n = n^2 + n\text{.}$Тут ми знаємо, що шукаємо квадратичну, оскільки другі відмінності постійні. $a_n = an^2 + bn + c\text{.}$Так як$a_0 = 0\text{,}$ ми знаємо$c= 0\text{.}$ Так просто вирішити систему\ begin {align*} 2\ amp = A + b\\ 6\ amp = 4a + 2b\ end {align*}

2

Складіть послідовності, які мають

1. 3, 3, 3, 3,... як його другі відмінності.
2. 1, 2, 3, 4, 5,... як його треті відмінності.
3. 1, 2, 4, 8, 16,... як його 100-ті відмінності.

3

Розглянемо послідовність$1, 3, 7, 13, 21, \ldots\text{.}$ Поясніть, як ви знаєте, замкнута формула для послідовності буде квадратичною. Потім «вгадайте» правильну формулу, порівнявши цю послідовність з квадратами$1, 4, 9, 16, \ldots$ (не використовуйте поліноміальну підгонку).

Рішення

Перші відмінності є,$2, 4, 6, 8, \ldots\text{,}$ а другі відмінності є$2, 2, 2, \ldots\text{.}$ Таким чином, вихідна послідовність$\Delta^2$ -постійна, тому може бути пристосована до квадратичного.

Викликати початкову послідовність$a_n\text{.}$ Розглянемо$a_n - n^2\text{.}$$0, -1, -2, -3, \ldots\text{.}$ Це дає Ця послідовність має замкнуту формулу$1-n$ (починаючи з$n = 1$), тому ми маємо$a_n - n^2 = 1-n$ або еквівалентно$a_n = n^2 - n + 1\text{.}$

4

Використовуйте аналогічну техніку, як і в попередній вправі, щоб знайти замкнуту формулу для послідовності.$2, 11, 34, 77, 146, 247,\ldots\text{.}$

5

У свій час простою пірати-привиди насолоджуються укладанням гарматних ядер у трикутні піраміди на основі (ака, тетраедрони), як ті, що зображені тут:

Зверніть увагу, що на малюнку праворуч є деякі гарматні ядра (насправді лише одне), які ви не можете побачити. На наступному малюнку буде 4 гарматних ядра, які ви не можете побачити. Стеки не пустотілі.

Пірати дивуються, скільки гарматних ядер буде потрібно для побудови піраміди висотою 15 шарів (таким чином, побивши світовий рекорд штабелювання гарматного ядра). Чи можете ви допомогти?

1. Нехай$P(n)$ позначимо кількість гарматних ядер, необхідних для створення піраміди високими$n$ шарами. Так$P(1) = 1\text{,}$$P(2) = 4\text{,}$ і так далі. Розрахувати$P(3)\text{,}$$P(4)$ і$P(5)\text{.}$
2. Використовуйте підгонку поліномів, щоб знайти замкнуту формулу для$P(n)\text{.}$ Покажіть свою роботу.
3. Дайте відповідь на питання пірата: скільки гарматних ядер їм потрібно, щоб зробити піраміду висотою в 15 шарів?

6

Припустимо,$a_n = n^2 + 3n + 4\text{.}$ знайдіть замкнуту формулу для послідовності відмінностей шляхом обчислення$a_n - a_{n-1}\text{.}$

Відповідь

$a_{n-1} = (n-1)^2 + 3(n-1) + 4 = n^2 + n + 2\text{.}$Таким чином,$a_n - a_{n-1} = 2n+2\text{.}$ Зверніть увагу, що це лінійний (арифметичний). Ми можемо перевірити, що ми правильні. Послідовність$a_n$ є$4, 8, 14, 22, 32, \ldots$ і послідовність відмінностей, таким чином$4, 6, 8, 10,\ldots$, що узгоджується з$2n+2$ (якщо ми почнемо з$n = 1$).

7

Повторіть наведене вище припускаючи цей час$a_n = an^2 + bn + c\text{.}$ Тобто довести, що кожна квадратична послідовність має арифметичні відмінності.

8

Чи можете ви використовувати поліноміальну підгонку, щоб знайти формулу для$n$ го члена послідовності 4, 7, 11, 18, 29, 47,...? Поясніть, чому чи чому ні.

9

Чи буде послідовність відмінностей$2, 6, 18, 54, 162, \ldots$ коли-небудь постійною?$n$ Поясніть.

10

Розглянемо послідовності$2, 5, 12, 29, 70, 169, 408,\ldots$ (з$a_0 = 2$).

1. Опишіть швидкість зростання цієї послідовності.
2. Знайдіть рекурсивне визначення послідовності.
3. Знайдіть замкнуту формулу для послідовності.
4. Якщо ви подивитеся на послідовність відмінностей між термінами, а потім послідовність другої відмінності, послідовність третіх відмінностей і так далі, ви коли-небудь отримаєте постійну послідовність? Поясніть, як ви знаєте

2.4: Вирішення відносин повторення

1

Знайдіть наступні два члени на$(a_n)_{n\ge 0}$ початку$3, 5, 11, 21, 43, 85\ldots.\text{.}$ Потім дайте рекурсивне визначення послідовності. Нарешті, скористайтеся технікою характерного кореня, щоб знайти замкнуту формулу для послідовності.

Відповідь

171 і 341. $a_n = a_{n-1} + 2a_{n-2}$з$a_0 = 3$ і$a_1 = 5\text{.}$ Закрита формула:$a_n = \frac{8}{3}2^n + \frac{1}{3}(-1)^n\text{.}$ Для цього розв'яжіть характеристичний многочлен,$x^2 - x - 2\text{,}$ щоб отримати характерні$x = 2$ корені і$x=-1\text{.}$ потім вирішити систему\ begin {align*} 3\ amp = a + b\\ 5\ amp = 2a - b\ end {align*}

2

Вирішити зв'язок повторення за$a_n = a_{n-1} + 2^n$ допомогою$a_0 = 5\text{.}$

Відповідь

$a_n = 3 + 2^{n+1}\text{.}$Тут ми повинні використовувати телескопічну або ітерацію. Наприклад, телескопічна дає

\ begin {align*} a_1 - a_0\ amp = 2^1\ a_2 - a_1\ amp = 2^2\ a_3 - a_2\ амп = 2^3\\ vdots\ амп\ vdots\\ a_n - a_ {n-1}\ амп = 2^n\ кінець {align*}

який сумує до$a_n - a_0 = 2^{n+1} - 2$ (використовуючи метод множення-shift-віднімання з розділу 2.2 для правого боку). Заміна$a_0 = 5$ і рішення для$a_n$ завершує рішення.

3

Показати, що$4^n$ є розв'язком рекуррентного відношення$a_n = 3a_{n-1} + 4a_{n-2}\text{.}$

Відповідь

Ми стверджуємо$a_n = 4^n$ роботи. Підключіть його:$4^n = 3(4^{n-1}) + 4(4^{n-2})\text{.}$ Це працює - просто спростіть праву сторону.

4

Знайти рішення рекуррентного відношення$a_n = 3a_{n-1} + 4a_{n-2}$ з початковими термінами$a_0 = 2$ і$a_1 = 3\text{.}$

Відповідь

За технікою характерного кореня. $a_n = 4^n + (-1)^n\text{.}$

5

Знайти рішення рекуррентного відношення$a_n = 3a_{n-1} + 4a_{n-2}$ з початковими термінами$a_0 = 5$ і$a_1 = 8\text{.}$

6

Вирішити зв'язок повторення$a_n = 2a_{n-1} - a_{n-2}\text{.}$

1. Яке рішення, якщо початкові терміни є$a_0 = 1$ і$a_1 = 2\text{?}$
2. Якими повинні бути початкові терміни, щоб$a_9 = 30\text{?}$
3. Для яких$x$ існують початкові терміни, які складають$a_9 = x\text{?}$

7

Вирішити зв'язок повторення$a_n = 3a_{n-1} + 10a_{n-2}$ з початковими термінами$a_0 = 4$ і$a_1 = 1\text{.}$

8

Припустимо, що$r^n$ і$q^n$ обидва рішення рекуррентного відношення форми$a_n = \alpha a_{n-1} + \beta a_{n-2}\text{.}$ Доведіть, що$c\cdot r^n + d \cdot q^n$ це також рішення рекуррентного відношення, для будь-яких констант$c, d\text{.}$

9

Подумайте про чарівну цукеркову машину у вашому сусідньому продуктовому магазині. Припустимо, що з першого разу вводиться чверть в автомат виходить 1 Скиттл. Другий раз, 4 кеглі, третій раз 16 кеглів, четвертий раз 64 кеглі і т.д.

1. Знайдіть як рекурсивну, так і закриту формулу для того, скільки кеглів отримує n клієнт.
2. Перевірте рішення для закритої формули, вирішивши відношення повторення за допомогою методу Характеристичного кореня.

10

У вас є доступ до$1 \times 1$ плитки, які поставляються в 2 різних кольорах і$1\times 2$ плитки, які приходять в 3 різних кольорах. Ми хочемо з'ясувати, скільки різних конструкцій$1 \times n$ контурів ми можемо зробити з цих плиток.

1. Знайти рекурсивне визначення$a_n$ послідовності шляхів довжини$n\text{.}$
2. Вирішіть зв'язок повторення за допомогою методу характерного кореня.

11

$a_n$Дозволяти кількість конструкцій$1 \times n$ плитки, які ви можете зробити за допомогою$1 \times 1$ квадратів, доступних у 4 кольорах та$1 \times 2$ доміно, доступних у 5 кольорах.

1. Спочатку знайдіть рецидивне відношення для опису проблеми. Поясніть, чому відношення повторення є правильним (в контексті проблеми).
2. Випишіть перші 6 членів послідовності$a_1, a_2, \ldots\text{.}$
3. Вирішити зв'язок повторення. Тобто знайти замкнуту формулу для$a_n\text{.}$

12

Розглянемо відношення рецидивів$a_n = 4a_{n-1} - 4a_{n-2}\text{.}$

1. Знайдіть загальне рішення відношення повторення (остерігайтеся повторюваного кореня).
2. Знайдіть рішення, коли$a_0 = 1$ і$a_1 = 2\text{.}$
3. Знайдіть рішення, коли$a_0 = 1$ і$a_1 = 8\text{.}$

2.5: Індукція

1

Використовуйте індукцію, щоб довести все$n \in \N$ це$\d\sum_{k=0}^n 2^k = 2^{n+1} - 1\text{.}$

Рішення

Доказ

Ми повинні довести, що$1 + 2 + 2^2 + 2^3 + \cdots +2^n = 2^{n+1} - 1$ для всіх$n \in \N\text{.}$ Таким чином,$P(n)$ нехай твердження$1 + 2 + 2^2 + \cdots + 2^n = 2^{n+1} - 1\text{.}$ Ми доведемо, що$P(n)$ це вірно для всіх$n \in \N\text{.}$ Спочатку ми встановлюємо базовий випадок,$P(0)\text{,}$ який стверджує, що$1 = 2^{0+1} -1\text{.}$ Оскільки$2^1 - 1 = 2 - 1 = 1\text{,}$ ми бачимо, що$P(0)$ це правда. Тепер про індуктивному випадку. Припустимо,$P(k)$ що вірно для довільного$k \in \N\text{.}$ Тобто,$1 + 2 + 2^2 + \cdots + 2^k = 2^{k+1} - 1\text{.}$ Ми повинні показати, що$P(k+1)$ це правда (тобто, що$1 + 2 + 2^2 + \cdots + 2^{k+1} = 2^{k+2} - 1$). Для цього починаємо з лівого боку$P(k+1)$ і працюємо з правого боку:

\ begin {вирівнювати*} 1 + 2 ^ 2 ^ 2 +\ cdots + 2^ {k+1} =\ ампер ~ 2^ {к+1} - 1 + 2^ {к+1}\ ампер\ текст {за індуктивною гіпотезою}\\ =\ ампер ~ 2\ cdot 2^ {k+1} - 1\ ампер\ =\ ампер ~ 2^ {к+2} - 1\ ампер\\ кінець {вирівнювати*}

Таким чином$P(k+1)$, вірно, так за принципом математичної індукції,$P(n)$ вірно для всіх.$n \in \N\text{.}$

2

Доведіть,$7^n - 1$ що кратна 6 для всіх$n \in \N\text{.}$

Рішення

Доказ

$P(n)$Дозволяти бути твердженням «$7^n - 1$кратна 6». Ми покажемо$P(n)$ це правда для всіх$n \in \N\text{.}$ Спочатку ми встановлюємо базовий випадок,$P(0)\text{.}$ Оскільки$7^0 - 1 = 0\text{,}$ і$0$ кратний 6,$P(0)$ це правда. Тепер про індуктивному випадку. Припустимо,$P(k)$ тримає для довільного$k \in \N\text{.}$$7^k - 1$ Тобто, кратне 6, або іншими словами,$7^k - 1 = 6j$ для деякого цілого числа$j\text{.}$ Тепер розглянемо$7^{k+1} - 1\text{:}$

\ begin {вирівнювати*} 7^ {k+1} - 1 ~\ amp = 7^ {k+1} - 7 + 6\ ампер\ текст {за розумністю:} -1 = -7 + 6\\ ампер = 7 (7^k - 1) + 6\ ампер\ текст {фактор з перших двох членів}\\ ампер = 7 (6j) + 6\ ампер\ текст {індуктивна гіпотеза}\\ ампер = 6 (7j + 1)\ amp\ text {фактор з 6}\ end {align*}

Тому$7^{k+1} - 1$ кратна 6, або іншими словами,$P(k+1)$ вірно. Тому за принципом математичної індукції,$P(n)$ вірно для всіх$n \in \N\text{.}$

3

Доведіть, що$1 + 3 + 5 + \cdots + (2n-1) = n^2$ для всіх$n \ge 1\text{.}$

Рішення

Доказ

$P(n)$Нехай твердження$1+3 +5 + \cdots + (2n-1) = n^2\text{.}$ Ми доведемо, що$P(n)$ вірно для всіх$n \ge 1\text{.}$ Спочатку базовий випадок,$P(1)\text{.}$ Ми маємо$1 = 1^2$ який є істинним, так і$P(1)$ встановлюється. Тепер індуктивний випадок. Припустимо, що$P(k)$ це вірно для деяких фіксованих довільних$k \ge 1\text{.}$ Тобто,$1 + 3 + 5 + \cdots + (2k-1) = k^2\text{.}$ Ми тепер доведемо, що$P(k+1)$ також вірно (тобто, що$1 + 3 + 5 + \cdots + (2k+1) = (k+1)^2$). Починаємо з лівого боку$P(k+1)$ і працюємо з правого боку:

\ begin {вирівнювати*} 1 + 3 + 5 +\ cdots + (2k-1) + (2к+1) ~\ ампер = k^2 + (2k+1)\ ампер\ текст {по інд. гіп.}\\ amp = (k+1) ^2\ amp\ текст {факторингом}\ кінець {вирівнювати*}

Таким чином$P(k+1)$ тримається, так за принципом математичної індукції,$P(n)$ вірно для всіх$n \ge 1\text{.}$

4

Доведіть, що$F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1$ де$F_n$ є число Фібоначчі.$n$

Рішення

Доказ

$P(n)$Дозволяти бути твердженням$F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1\text{.}$ Ми покажемо,$P(n)$ що вірно для всіх$n \ge 0\text{.}$ Спочатку базовий випадок легко, тому що$F_0 = 0$ і$F_1 = 1$ так$F_0 = F_1 - 1\text{.}$ Тепер розглянемо індуктивний випадок. Припустимо,$P(k)$ це правда, тобто припустимо,$F_0 + F_2 + F_4 + \cdots + F_{2k} = F_{2k+1} - 1\text{.}$ щоб встановити$P(k+1)$ ми працюємо зліва направо:

\ почати {вирівнювати*} F_0 + F_2 +\ cdots + F_ {2k} + F_ {2k+2} ~\ ампер = F_ {2k+1} - 1 + F_ {2k+2}\ ампер\ текст {по інд. гіп.}\\ ампер = F_ {2к+1} + F_ {2к+2} - 1\ ампер\\ амп = F_ {2k+3} - 1\ amp\ text {по рекурсивному def.} \ end {вирівнювати*}

Тому$F_0 + F_2 + F_4 + \cdots + F_{2k+2} = F_{2k+3} - 1\text{,}$, що можна сказати,$P(k+1)$ тримає. Тому за принципом математичної індукції,$P(n)$ вірно для всіх$n \ge 0\text{.}$

5

Доведіть, що$2^n \lt n!$ для всіх$n \ge 4\text{.}$ (нагадаємо,$n! = 1\cdot 2 \cdot 3 \cdot \cdots\cdot n\text{.}$)

Рішення

Доказ

$P(n)$Дозволяти бути твердженням$2^n \lt n!\text{.}$ Ми покажемо$P(n)$ це правда для всіх$n \ge 4\text{.}$ По-перше, ми перевіряємо базовий випадок і бачимо, що так,$2^4 \lt 4!$ (як$16 \lt 24$) так$P(4)$ вірно. Тепер про індуктивному випадку. Припустимо$P(k)$, вірно для довільного$k \ge 4\text{.}$ Тобто,$2^k \lt k!\text{.}$ Тепер розглянемо$P(k+1)\text{:}$$2^{k+1} \lt (k+1)!\text{.}$ Щоб довести це, ми починаємо з лівого боку і працюємо з правого боку.

\ begin {вирівнювати*} 2^ {к+1} ~\ ампер = 2\ cdot 2^k\ ампер\\ ампер\ lt 2\ cdot k! \ amp\ text {за індуктивною гіпотезою}\\ amp\ lt (k+1)\ cdot k! \ амп\ текст {так як} k+1\ gt 2\\ амп = (к+1)! \ amp\ end {вирівнювати*}

Тому$2^{k+1} \lt (k+1)!$ так ми встановили.$P(k+1)\text{.}$ Таким чином, за принципом математичної індукції$P(n)$ вірно для всіх.$n \ge 4\text{.}$

6

Доведіть, шляхом математичної індукції, що$F_0 + F_1 + F_2 + \cdots + F_{n} = F_{n+2} - 1\text{,}$ де$F_n$ є$n$ й число Фібоначчі ($F_0 = 0\text{,}$$F_1 = 1$і$F_n = F_{n-1} + F_{n-2}$).

7

Зомбі Ейлер та Зомбі Коші, два відомих математики-зомбі, щойно підписалися на акаунти Twitter. Через один день зомбі Коші має більше послідовників, ніж зомбі Ейлер. Кожен день після цього кількість нових послідовників Zombie Cauchy точно така ж, як кількість нових послідовників Zombie Euler (і ні втрачають жодних послідовників). Поясніть, як доказ математичної індукції може показати, що кожен день після першого дня Зомбі Коші матиме більше послідовників, ніж Зомбі Ейлер. Тобто поясніть, що таке базовий випадок та індуктивний випадок, і чому вони разом доводять, що Зомбі Коші матиме більше послідовників на 4-й день.

8

Знайдіть найбільшу кількість очок, які футбольна команда не може отримати точно, використовуючи лише 3-очкові поля та 7-очкові тачдауни (ігноруйте можливості безпеки, пропущені додаткові очки та дві конвертації очок). Доведіть, що ваша відповідь правильна за допомогою математичної індукції.

9

Довести, що суму$n$ квадратів можна знайти наступним чином

\ begin {рівняння*} 1^2 +2^2 +3^2+... +n^2 =\ розрив {n (n+1) (2n+1)} {6}\ end {рівняння*}

10

Що не так з наступним «доказом» того «факту», що$n+3 = n+7$ для всіх значень$n$ (крім звичайно, що річ, яку він стверджує довести, є помилковою)?

Доказ

$P(n)$Дозволяти твердження, що$n + 3 = n + 7\text{.}$ Ми доведемо,$P(n)$ що вірно для всіх$n \in \N\text{.}$ Припустимо, для індукції$P(k)$ це правда. Тобто,$k+3 = k+7\text{.}$ Ми повинні показати, що$P(k+1)$ це правда. Тепер так$k + 3 = k + 7\text{,}$ додайте по 1 в обидві сторони. Це дає$k + 3 + 1 = k + 7 + 1\text{.}$ Перегрупування$(k+1) + 3 = (k+1) + 7\text{.}$ Але це просто$P(k+1)\text{.}$ Таким чином, за принципом математичної індукції$P(n)$ вірно для всіх.$n \in \N\text{.}$

Рішення

Єдина проблема полягає в тому, що ми ніколи не встановили базовий випадок. Звичайно, коли$n = 0\text{,}$$0+3 \ne 0+7\text{.}$

11

Доказ в попередній проблемі не працює. Але якщо ми змінимо «факт», ми можемо отримати робочий доказ. Доведіть, що$n + 3 \lt n + 7$ для всіх значень$n \in \N\text{.}$ Ви можете зробити це доказ за допомогою алгебри (без індукції), але мета цієї вправи полягає в тому, щоб виписати дійсний індукційний доказ.

Відповідь

Доказ

Дозвольте$P(n)$ бути твердженням, що$n + 3 \lt n + 7\text{.}$ Ми доведемо, що$P(n)$ це вірно для всіх$n \in \N\text{.}$ По-перше, зверніть увагу, що базовий випадок тримає:$0+3 \lt 0+7\text{.}$ Тепер припустимо, що для індукції$P(k)$ це правда. Тобто,$k+3 \lt k+7\text{.}$ Ми повинні показати, що$P(k+1)$ це правда. Тепер так$k + 3 \lt k + 7\text{,}$ додайте по 1 в обидві сторони. Це дає$k + 3 + 1 \lt k + 7 + 1\text{.}$ Перегрупування$(k+1) + 3 \lt (k+1) + 7\text{.}$ Але це просто$P(k+1)\text{.}$ Таким чином, за принципом математичної індукції$P(n)$ вірно для всіх.$n \in \N\text{.}$

$\square$

12

Знайдіть недолік в наступному «доказі» того «факту», що$n \lt 100$ для кожного$n \in \N\text{.}$

Доказ

Дозвольте$P(n)$ бути твердженням$n \lt 100\text{.}$ Ми доведемо$P(n)$ вірно для всіх$n \in \N\text{.}$ Спочатку ми встановлюємо базовий випадок: коли$n = 0\text{,}$$P(n)$ це правда, тому що$0 \lt 100\text{.}$ Тепер для індуктивного кроку, припускаємо, що$P(k)$ це правда. Тобто,$k \lt 100\text{.}$ тепер якщо$k \lt 100\text{,}$ тоді$k$ якесь число, як 80. Звичайно$80+1 = 81$, який все ще менше 100. Так$k +1 \lt 100$ само, як і. Але це те, що$P(k+1)$ стверджує, тому ми показали, що$P(k) \imp P(k+1)\text{.}$ Таким чином, за принципом математичної індукції,$P(n)$ вірно для всіх$n \in \N\text{.}$

Рішення

Проблема тут полягає в тому, що$P(0)$ while є істинним, і в той час як$P(k) \imp P(k+1)$ для деяких значень$k\text{,}$ існує принаймні одне значення$k$ (а саме$k = 99$), коли цей підтекст не вдається. Для дійсного доказу шляхом індукції,$P(k) \imp P(k+1)$ має бути істинним для всіх значень,$k$ більших або рівних базовому випадку.

13

Поки вищевказаний доказ не працює (краще не так як твердження, яке він намагається довести, є помилковим!) ми можемо довести щось подібне. Доведіть, що існує строго зростаюча$a_1, a_2, a_3, \ldots$ послідовність чисел (не обов'язково цілі числа) такі, що$a_n \lt 100$ для всіх$n \in \N\text{.}$ (Строго збільшення ми маємо на увазі$a_n \lt a_{n+1}$ для всіх$n\text{.}$ Таким чином, кожен член повинен бути більше, ніж останній.)

Рішення

Доказ

Дозвольте$P(n)$ бути твердженням «існує строго зростаюча послідовність$a_1, a_2, \ldots, a_n$ з$a_n \lt 100\text{.}$» Ми доведемо$P(n)$ вірно для всіх$n \ge 1\text{.}$ Спочатку встановлюємо базовий випадок:$P(1)$ каже, що є єдине число$a_1$ з$a_1 \lt 100\text{.}$ Це вірно - візьміть$a_1 = 0\text{.}$ Тепер для індуктивний крок, припустимо$P(k)$, вірно. Тобто існує строго зростаюча послідовність$a_1, a_2, a_3, \ldots, a_k$ з$a_k \lt 100\text{.}$ Тепер розглянемо цю послідовність, плюс ще один термін,$a_{k+1}$ який більше,$a_k$ але менше$100\text{.}$ такого числа існує, наприклад, середнє значення між$a_k$ 100. Отже,$P(k+1)$ це правда, тому ми показали, що$P(k) \imp P(k+1)\text{.}$ Таким чином, за принципом математичної індукції,$P(n)$ вірно для всіх$n \in \N\text{.}$

14

Що не так з наступним «доказом» того «факту», що для всіх$n \in \N\text{,}$ число$n^2 + n$ непарне?

Доказ

$P(n)$Дозволяти твердження «$n^2 + n$це непарно». Доведемо,$P(n)$ що вірно для всіх$n \in \N\text{.}$ Припустимо для індукції, що вірно,$k^2 + k$ тобто непарно.$P(k)$ Тепер розглянемо твердження$P(k+1)\text{.}$ Now$(k+1)^2 + (k+1) = k^2 + 2k + 1 + k + 1 = k^2 + k + 2k + 2\text{.}$ By індуктивної гіпотези,$k^2 + k$ непарне, і звичайно$2k + 2$ парне. Непарний плюс парний завжди непарний, тому$(k+1)^2 + (k+1)$ непарний. Тому за принципом математичної індукції,$P(n)$ вірно для всіх$n \in \N\text{.}$

$\square$

15

Тепер дайте дійсний доказ (шляхом індукції, навіть якщо ви можете зробити це без використання індукції) твердження, «бо все$n \in \N\text{,}$ число$n^2 + n$ парне».

16

Доведіть, що існує послідовність позитивних дійсних чисел,$a_0, a_1, a_2, \ldots$ таких, що$a_0 + a_1 + a_2 + \cdots + a_n$ часткова сума строго менше, ніж$2$ для всіх$n \in \N\text{.}$ Підказка: подумайте про те, як ви могли б визначити, що$a_{k+1}$ таке зробити індукційний аргумент роботи.

Рішення

Ідея полягає в тому, щоб визначити послідовність так, щоб$a_n$ вона була меншою за відстань між попередньою частковою сумою і 2. Таким чином, коли ви додаєте його до наступної часткової суми, часткова сума все ще менше 2. Ви можете зробити це заздалегідь, або використовувати розумний$P(n)$ в індукційному доказ.

Доказ

$P(n)$Дозволяти бути твердженням, «є послідовність позитивних дійсних чисел$a_0, a_1, a_2, \ldots, a_n$ такий, що$a_0 + a_1 + a_2 + \cdots + a_n \lt 2\text{.}$»

Базовий випадок: Виберіть будь-який$a_0 \lt 2\text{.}$

Індуктивний випадок: Припустимо, що$a_1 + a_2 + \cdots + a_k \lt 2\text{.}$ тепер нехай$a_{k+1} = \frac{2- a_1 + a_2 + \cdots + a_k}{2}\text{.}$ тоді$a_1 + a_2 + \cdots +a_k + a_{k+1} \lt 2\text{.}$

Тому за принципом математичної індукції$P(n)$ вірно для всіх$n \in \N$

17

Доведіть, що кожне натуральне число або ступінь 2, або може бути записана як сума різних степенів 2.

Рішення

Доказ буде сильною індукцією.

Доказ

$P(n)$Дозволяти твердження «$n$це або сила 2, або може бути записана як сума різних повноважень 2». Ми покажемо,$P(n)$ що вірно для всіх$n \ge 1\text{.}$

Базовий випадок:$1 = 2^0$ це сила 2, так і$P(1)$ вірно.

Індуктивний випадок: Припустимо$P(k)$, вірно для всіх$k \lt n\text{.}$ Тепер, якщо$n$ це сила 2, ми закінчили. Якщо ні, нехай$2^x$ буде найбільша сила 2 строго менше, ніж$n\text{.}$ Розглянемо,$n - 2^x\text{,}$ яке є меншим числом, насправді менше, ніж обидва$n$ і$2^x\text{.}$ Таким чином$n-2^x$, або сила 2, або може бути записана як сума різних повноважень 2, але жодна з них не буде $2^x\text{,}$так що разом з$2^x$ ми написали$n$ як суму різних повноважень 2.

Тому за принципом (сильної) математичної індукції,$P(n)$ вірно для всіх$n \ge 1\text{.}$

18

Доведіть, використовуючи сильну індукцію, що кожне натуральне число або число Фібоначчі, або може бути записано як сума різних чисел Фібоначчі.

19

Використовуйте індукцію, щоб довести, що якщо всі$n$ люди тиснуть один одному руки, то загальна кількість рукостискань дорівнює$\frac{n(n-1)}{2}\text{.}$

Рішення

Зверніть увагу, ми вже довели це без використання індукції, але дивлячись на неї індуктивно проливає світло на проблему (і це весело).

Доказ

Нехай$P(n)$ буде твердження «коли$n$ люди тиснуть один одному руки, відбувається сукупність$\frac{n(n-1)}{2}$ рукостискань».

Базовий випадок: Коли$n=2\text{,}$ буде одне рукостискання, і$\frac{2(2-1)}{2} = 1\text{.}$ Таким чином$P(2)$ вірно.

Індуктивний випадок: Припустимо$P(k)$, вірно для довільних$k\ge 2$ (що кількість рукостискань серед$k$ людей - це$\frac{k(k-1)}{2}\text{.}$ Що станеться, якщо з'являється$k+1$ st людина? Скільки нових рукостискань відбувається? Нова людина повинна потиснути руку всім там, що є$k$ новими рукостисканнями. Тож загальна сума тепер у$\frac{k(k-1)}{2} + k = \frac{(k+1)k}{2}\text{,}$ міру необхідності.

Тому за принципом математичної індукції$P(n)$ вірно для всіх$n \ge 2\text{.}$

20

Припустимо, що конкретне$x$ дійсне число має властивість, яка$x + \frac{1}{x}$ є цілим числом. Доведіть, що$x^n + \frac{1}{x^n}$ це ціле число для всіх натуральних чисел$n\text{.}$

Рішення

Коли$n = 0\text{,}$ ми отримуємо$x^0 +\frac{1}{x^0} = 2$ і коли$n = 1\text{,}$$x + \frac{1}{x}$ ціле число, так що базовий випадок тримає. Тепер припустимо, що результат тримає для всіх натуральних чисел,$n \lt k\text{.}$ зокрема, ми знаємо, що$x^{k-1} + \frac{1}{x^{k-1}}$ і$x + \frac{1}{x}$ обидва цілі числа. При цьому їх добуток також є цілим числом. Але,

\ почати {вирівнювати*}\ ліворуч (x^ {k-1} +\ розрив {1} {x^ {k-1}}\ праворуч)\ вліво (х +\ розрив {1} {x}\ праворуч)\ ампер = x^k +\ frac {x^ {k-1}} {x} +\ гідророзриву {x} {x} {x^ {k-1} x^k}\\ ампер = x^k +\ розрив {1} {x^k} + x^ {k-2} +\ гідророзриву {1} {x^ {k-2}}\ end {align*}

Зверніть увагу також, що$x^{k-2} + \frac{1}{x^{k-2}}$ це ціле число за індукційною гіпотезою, тому ми можемо зробити висновок, що$x^k + \frac{1}{x^k}$ це ціле число.

21

Використовуйте індукцію, щоб довести,$\d\sum_{k=0}^n {n \choose k} = 2^n\text{.}$ що Тобто сума$n$ го рядка трикутника Паскаля дорівнює$2^n\text{.}$

22

Використовуйте індукцію, щоб довести${4 \choose 0} + {5 \choose 1} + {6 \choose 2} + \cdots + {4+n \choose n} = {5+n \choose n}\text{.}$ (Це приклад теореми хокейної ключки.)

23

Використовуйте правило добутку для логарифмів ($\log(ab) = \log(a) + \log(b)$), щоб довести, шляхом індукції на$n\text{,}$ це$\log(a^n) = n \log(a)\text{,}$ для всіх натуральних чисел$n \ge 2\text{.}$

Рішення

Ідея тут полягає в тому, що якщо взяти логарифм$a^n\text{,}$ ми можемо збільшити$n$ на 1, якщо ми помножимо на інший$a$ (всередині логарифма). Це призводить до додавання ще 1$\log(a)$ до загальної кількості.

Доказ

$P(n)$Дозволяти бути$\log(a^n) = n \log(a)\text{.}$ твердженням Базовий випадок,$P(2)$ істинно, тому що$\log(a^2) = \log(a\cdot a) = \log(a) + \log(a) = 2\log(a)\text{,}$ за правилом добутку для логарифмів. Тепер припустимо, для індукції,$P(k)$ це правда. Тобто,$\log(a^k) = k\log(a)\text{.}$ Вважайте, що$\log(a^{k+1})\text{.}$ ми маємо

\ begin {рівняння*}\ лог (a^ {k+1}) =\ лог (a^k\ cdot a) =\ лог (a^k) +\ лог (a) = k\ log (a) +\ log (a)\ end {рівняння*}

з останньою рівністю за рахунок індуктивної гіпотези. Але це спрощує$(k+1) \log(a)\text{,}$ встановлення$P(k+1)\text{.}$ Тому за принципом математичної індукції,$P(n)$ вірно для всіх$n \ge 2\text{.}$

24

$f_1, f_2,\ldots, f_n$Дозволяти диференційовні функції. Доведіть, використовуючи індукцію, що

\ begin {рівняння*} (f_1 + f_2 +\ cdots + f_n) '= f_1' + f_2' +\ cdots + f_n'\ кінець {рівняння*}

Ви можете припустити$(f+g)' = f' + g'$ для будь-яких диференційованих функцій$f$ і$g\text{.}$

Підказка

Вам дозволяється припустити базовий випадок. Для індуктивного випадку згрупуйте всі, крім останньої функції, разом як одну суму функцій, потім застосуйте звичайне правило суми похідних, а потім індуктивну гіпотезу.

25

Припустимо$f_1, f_2, \ldots, f_n$, це диференційовні функції. Використовуйте математичну індукцію, щоб довести узагальнене правило добутку:

\ begin {рівняння*} (f_1 f_2 f_3\ cdots f_n) '= f_1' f_2 f_3\ cdots f_n + f_1 f_2' f_3\ cdots f_3\ cdots f_3\ cdots _n'\ end {рівняння*}

Ви можете припустити, що правило продукту для двох функцій є істинним.

Підказка

Для індуктивного кроку ми знаємо за правилом продукту для двох функцій, які

\ begin {рівняння*} (f_1f_2f_3\ cdots f_k f_ {k+1}) '= (f_1f_2f_3\ cdots f_k) 'f_ {k+1} + (f_1f_2f_3\ cdots f_k) f_ {k+1}'\ кінець {рівняння*}

Потім використовуйте індуктивну гіпотезу по першій сумі, і розподіліть.