2.S: Послідовності (резюме)

Template:MathJaxLevin

Досліджуйте!

Кожен день ваш запас чарівних шоколадних покритих еспресо бобів подвоюється (кожен з них розщеплюється навпіл), але потім ви їсте 5 з них. У вас є 10 на початку дня 0.

1. Випишіть перші кілька термінів послідовності. Потім дайте рекурсивне визначення послідовності та поясніть, як ви знаєте, що це правильно.
2. Доведіть, використовуючи індукцію, що остання цифра числа бобів у вас на$n$ й день завжди дорівнює 5 для всіх$n \ge 1\text{.}$
3. Знайдіть замкнуту формулу для$n$ го члена послідовності і доведіть її правильність шляхом індукції.

У цьому розділі ми досліджували послідовності та математичну індукцію. Спочатку вони можуть здатися не зовсім пов'язаними, але є посилання: рекурсивні міркування. Коли у нас багато випадків (може бути, нескінченно багато), часто простіше описати конкретний випадок, сказавши, як він відноситься до інших випадків, замість того, щоб описувати його абсолютно. Для послідовностей ми можемо описати$n$ той термін у послідовності, сказавши, як він пов'язаний з попереднім терміном. При показі твердження,$n$ що включає змінну true для всіх значень,$n\text{,}$ ми можемо описати, чому випадок for$n = k$ істинний на основі того, чому case for$n = k-1$ є істинним.

Хоча мислення про проблеми рекурсивно часто простіше, ніж думати про них абсолютно (принаймні після того, як ви звикнете думати таким чином), наша кінцева мета - вийти за межі цього рекурсивного опису. Для послідовностей ми хочемо знайти замкнуті формули для$n$ го члена послідовності. Для доказів ми хочемо знати, що твердження насправді вірно для конкретного$n$ (не тільки за припущенням, що твердження вірно для попереднього значення$n$). У цьому розділі ми побачили деякі методи переходу від рекурсивних описів до абсолютних описів.

• Якщо члени послідовності збільшуються на постійну різницю або постійне відношення (це обидва рекурсивні описи), то послідовності арифметичні або геометричні відповідно, і ми маємо закриті формули для кожного з них на основі початкових членів і загальної різниці або співвідношення.
• Якщо члени послідовності збільшуються зі швидкістю многочлена (тобто, якщо відмінності між долями утворюють послідовність з многочленной замкнутою формулою), то сама послідовність задається многочленной замкнутою формулою (ступеня на один більше, ніж послідовність відмінностей).
• Якщо члени послідовності збільшуються з експоненціальною швидкістю, то ми очікуємо, що замкнута формула для послідовності буде експоненціальною. Ці послідовності часто мають відносно приємні рекурсивні формули, і характерна коренева техніка дозволяє знайти замкнуту формулу для цих послідовностей.
• Якщо ми хочемо довести, що твердження є істинним для всіх значень$n$ (більше, ніж якесь перше невелике значення), і ми можемо описати, чому твердження істинне для$n = k$ означає, що твердження вірно, бо$n = k+1\text{,}$ тоді принцип математичної індукції дає нам, що твердження є true для всіх значень$n$ (більше базового випадку).

Протягом усього розділу ми намагалися зрозуміти, чому ці факти, перераховані вище, є правдивими. Частково це те, що докази, шляхом індукції чи ні, намагаються досягти: вони пояснюють, чому математичні істини насправді є істиною. Оскільки ми розвиваємо нашу здатність міркувати про математику, це гарна ідея, щоб переконатися, що методи наших міркувань є здоровими. Галузь математики, яка займається вирішенням питання про те, чи є міркування хорошим чи ні, є математичною логікою, предметом наступного розділу.

Огляд глави

1

Знайти$3 + 7 + 11+ \cdots + 427\text{.}$

Відповідь

$\frac{430\cdot 107}{2} = 23005\text{.}$

2

Розглянемо послідовність$2, 6, 10, 14, \ldots, 4n + 6\text{.}$

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

Відповідь

1. $n+2$ terms.
2. $4n+2\text{.}$
3. $\frac{(4n+8)(n+2)}{2}\text{.}$

3

Розглянемо послідовність, задану$a_n = 2\cdot 5^{n-1}\text{.}$

1. Знайдіть перші 4 члени послідовності. Що це за послідовність?
2. Знайти суму перших 25 членів. Тобто обчислити$\d\sum_{k=1}^{25}a_k\text{.}$

Відповідь

1. $2, 10, 50, 250, \ldots$ The sequence is geometric.
2. $\frac{2 - 2\cdot 5^{25}}{-4}\text{.}$

4

Розглянемо послідовність$5, 11, 19, 29, 41, 55,\ldots\text{.}$ Припустимо$a_1 = 5\text{.}$

1. Знайдіть замкнуту$a_n\text{,}$ формулу для$n$ го члена послідовності, записуючи кожен член у вигляді суми послідовності. Підказка: спочатку знайдіть$a_0\text{,}$, але ігноруйте її при згортанні суми.
2. Знову знайдіть замкнуту формулу, цього разу використовуючи або поліноміальну підгонку, або характерну кореневу техніку (залежно від того, що підходить). Покажіть свою роботу.
3. Знову знайдіть замкнуту формулу, цього разу розпізнавши послідовність як модифікацію якоїсь відомої послідовності. Поясніть.

5

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

\ begin {рівняння*} 4, 11, 20, 31, 44,\ ldots. \ end {рівняння*}

Відповідь

$a_n = n^2 + 4n - 1\text{.}$

6

Припустимо, замкнута формула для певної послідовності - многочлен 3 ступеня. Що можна сказати про закриту формулу для:

1. Послідовність часткових сум.
2. Послідовність другої відмінності.

Відповідь

1. Послідовність часткових сум буде поліномом 4 ступеня (його послідовність відмінностей буде вихідною послідовністю).
2. Послідовність другої відмінності буде поліном 1 ступеня - арифметична послідовність.

7

Розглянемо послідовність, задану рекурсивно$a_1 = 4\text{,}$$a_2 = 6$ і$a_n = a_{n-1} + a_{n-2}\text{.}$

1. Випишіть перші 6 членів послідовності.
2. Чи може замкнута формула для$a_n$ бути поліномом? Поясніть.

Відповідь

1. $4, 6, 10, 16, 26, 42, \ldots\text{.}$
2. Ні, прийняття відмінностей повертає початкову послідовність назад, тому відмінності ніколи не будуть постійними.

8

Послідовність$-1, 0, 2, 5, 9, 14\ldots$ має замкнуту формулу$a_n = \dfrac{(n+1)(n-2)}{2}\text{.}$ Використовуйте цей факт, щоб знайти замкнуту формулу для послідовності$4, 10, 18, 28, 40, \ldots\text{.}$

Відповідь

$b_n = (n+3)n\text{.}$

9

У пісні Дванадцять днів Різдва, моя справжня любов подарувала мені спочатку 1 подарунок, потім 2 подарунки та 1 подарунок, потім 3 подарунки, 2 подарунки та 1 подарунок тощо. Скільки подарунків моя справжня любов подарувала мені всім разом протягом дванадцяти днів?

10

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

1. Випишіть перші 5 членів послідовності, визначеної цим співвідношенням повторення.
2. Вирішити зв'язок повторення. Тобто знайти замкнуту формулу для$a_n\text{.}$

Відповідь

1. $1, 2, 16,68, 364, \ldots\text{.}$
2. $a_n = \frac{3}{7}(-2)^n + \frac{4}{7}5^n\text{.}$

11

Розглянемо зв'язок повторення$a_n = 2a_{n-1} + 8a_{n-2}\text{,}$ з початковими термінами$a_0 = 1$ і$a_1= 3\text{.}$

1. Знайдіть наступні два члени послідовності ($a_2$і$a_3$).
2. Вирішити зв'язок повторення. Тобто знайти замкнуту формулу для$n$ го члена послідовності.

Відповідь

1. $a_2 = 14\text{.}$ $a_3 = 52\text{.}$
2. $a_n = \frac{1}{6}(-2)^n + \frac{5}{6}4^n\text{.}$

12

Ваші чарівні шоколадні кролики відтворюються як кролики: кожен великий кролик щодня виробляє 2 нових міні-кролика, і кожен день кожен міні-кролик, народжений попереднім днем, виростає у великого кролика. Припустимо, ви починаєте з 2 міні-кроликів і жоден кролик ніколи не вмирає (або отримує з'їдений).

1. Випишіть перші кілька термінів послідовності.
2. Дайте рекурсивне визначення послідовності і поясніть, чому вона правильна.
3. Знайдіть замкнуту формулу для$n$ го члена послідовності.

Відповідь

1. У перший день ваші 2 міні-зайчика стають 2 великими зайчиками. На 2-й день ваші два великих зайчика виробляють 4 міні-кролика. На 3-й день у вас є 4 міні-зайчики (вироблені вашими 2 великими кроликами) плюс 6 великих кроликів (ваш оригінальний 2 плюс 4 нещодавно дозрілих зайчиків). На 4 день у вас буде$12$ mini bunnies (2 for each of the 6 large bunnies) plus 10 large bunnies (your previous 6 plus the 4 newly matured). The sequence of total bunnies is $2, 2, 6, 10, 22, 42\ldots$ starting with $a_0 = 2$ and $a_1 = 2\text{.}$
2. $a_n = a_{n-1} + 2a_{n-2}\text{.}$ This is because the number of bunnies is equal to the number of bunnies you had the previous day (both mini and large) plus 2 times the number you had the day before that (since all bunnies you had 2 days ago are now large and producing 2 new bunnies each).
3. Використовуючи характерну кореневу техніку, знаходимо$a_n = a2^n + b(-1)^n\text{,}$ and we can find $a$ and $b$ to give $a_n = \frac{4}{3}2^n + \frac{2}{3}(-1)^n\text{.}$

13

Доведіть наступні твердження за допомогою математичної індукції:

1. $n! \lt n^n$для$n \ge 2$
2. $\d\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} +\frac{1}{3\cdot 4}+\cdots + \frac{1}{n\cdot(n+1)} = \d\frac{n}{n+1}$для всіх$n \in \Z^+\text{.}$
3. $4^n - 1$кратна 3 для всіх$n \in \N\text{.}$
4. Найбільша сума поштових відправлень, яку ви не можете зробити точно за допомогою марок 4 та 9 центів, становить 23 центи.
5. Кожне парне число в квадраті ділиться на 4.

Відповідь

1. Підказка:$(n+1)^{n+1} > (n+1) \cdot n^{n}\text{.}$
2. Підказка: Це має бути схоже на інші докази суми. Останній біт зводиться до додавання дробів.
3. Підказка: Написати$4^{k+1} - 1 = 4\cdot 4^k - 4 + 3\text{.}$
4. Підказка: одна 9-центова марка - це 1 більше двох 4-центових марок, а сім 4-центових марок - це 1 більше трьох 9-центових марок.
5. Обережно, щоб насправді використовувати індукцію тут. Базовий випадок:$2^2 = 4\text{.}$ The inductive case: assume $(2n)^2$ is divisible by 4 and consider $(2n+2)^2 = (2n)^2 + 4n + 4\text{.}$ This is divisible by 4 because $4n +4$ clearly is, and by our inductive hypothesis, so is $(2n)^2\text{.}$

14

Доведіть$1^3 + 2^3 + 3^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ проведення для всіх за$n \ge 1\text{,}$ допомогою математичної індукції.

Хін

Це прямий індукційний доказ. Зверніть увагу, що вам потрібно буде спростити$\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3$ and get $\left(\frac{(n+1)(n+2)}{2}\right)^2\text{.}$

15

Припустимо$a_0 = 1\text{,}$$a_1 = 1$ і$a_n = 3a_{n-1} - 2a_{n-1}\text{.}$ Доведіть, використовуючи сильну індукцію, що$a_n = 1$ для всіх$n\text{.}$

Підказка

Є два базових випадки$P(0)$ and $P(1)\text{.}$ Then, for the inductive case, assume $P(k)$ is true for all $k \lt n\text{.}$ This allows you to assume $a_{n-1} = 1$ and $a_{n-2} = 1\text{.}$ Apply the recurrence relation.

16

Доведіть, використовуючи сильну індукцію, що кожне натуральне число може бути записано як сума різних ступенів 2. Наприклад,$13 = 1 + 4 + 8 = 2^0 + 2^2 + 2^3\text{.}$

Відповідь

Зауважте, що$1 = 2^0\text{;}$ this is your base case. Now suppose $k$ can be written as the sum of distinct powers of 2 for all $1\le k \le n\text{.}$ We can then write $n$ as the sum of distinct powers of 2 as follows: subtract the largest power of 2 less than $n$ from $n\text{.}$ That is, write $n = 2^j + k$ for the largest possible $j\text{.}$ But $k$ is now less than $n\text{,}$ and also less than $2^j\text{,}$ so write $k$ as the sum of distinct powers of 2 (we can do so by the inductive hypothesis). Thus $n$ can be written as the sum of distinct powers of 2 for all $n \ge 1\text{.}$

17

Доведіть, використовуючи індукцію, що кожен набір, що містить$n$ елементи, має$2^n$ різні підмножини для будь-якого$n \ge 1\text{.}$

Відповідь

Нехай$P(n)$ be the statement, “every set containing $n$ elements has $2^n$ different subsets.” We will show $P(n)$ is true for all $n \ge 1\text{.}$ Base case: Any set with 1 element $\{a\}$ has exactly 2 subsets: the empty set and the set itself. Thus the number of subsets is $2= 2^1\text{.}$ Thus $P(1)$ is true. Inductive case: Suppose $P(k)$ is true for some arbitrary $k \ge 1\text{.}$ Thus every set containing exactly $k$ elements has $2^k$ different subsets. Now consider a set containing $k+1$ elements: $A = \{a_1, a_2, \ldots, a_k, a_{k+1}\}\text{.}$ Any subset of $A$ must either contain $a_{k+1}$ or not. In other words, a subset of $A$ is just a subset of $\{a_1, a_2,\ldots, a_k\}$ with or without $a_{k+1}\text{.}$ Thus there are $2^k$ subsets of $A$ which contain $a_{k+1}$ and another $2^{k+1}$ subsets of $A$ which do not contain $a^{k+1}\text{.}$ This gives a total of $2^k + 2^k = 2\cdot 2^k = 2^{k+1}$ subsets of $A\text{.}$ But our choice of $A$ was arbitrary, so this works for any subset containing $k+1$ elements, so $P(k+1)$ is true. Therefore, by the principle of mathematical induction, $P(n)$ is true for all $n \ge 1\text{.}$