Proof by induction
Введено| English | Значение |
|---|---|
| positive integer/ˈpɒzɪtɪv ˈɪntɪdʒə/ | положительное целое число |
| mathematical induction/ˌmæθɪˈmætɪkl ɪnˈdʌkʃn/ | математическая индукция |
| base case/beɪs keɪs/ | базовый случай |
| inductive step/ɪnˈdʌktɪv step/ | индуктивный переход |
| inductive hypothesis/ɪnˈdʌktɪv haɪˈpɒθəsɪs/ | предположение индукции |
| divisible/dɪˈvɪzɪbl/ | кратное |
| conjecture/kənˈdʒektʃə/ | гипотеза |
| factorial/fækˈtɔːrɪəl/ | факториал |
Повторяемое правило должно начинаться откуда-то
- Проверка закономерности для первых нескольких положительных целых чисел не может установить бесконечное число случаев. Математическая индукция связывает первое истинное утверждение с правилом, ведущим к каждому последующему.
- Базовый случай запускает цепочку. Индукционный переход доказывает условную связь для произвольного допустимого целого числа, а не только для следующего числа в короткой таблице.
Изображение домино иллюстрирует два отдельных требования: начальную истину и связь, работающую на каждой последующей позиции.
A starting truth and a general forward link
The base case P(n₀) and P(k)⇒P(k+1) for every k≥n₀ together establish P(n) for all integers n≥n₀.
Сформулируйте точно то, что доказывается
- Запишите утверждение $P(n)$ и диапазон целых чисел, начиная с $n_0$. Проверьте $P(n_0)$ напрямую, используя заданное начальное условие при необходимости. Затем предположите $P(k)$ для произвольного целого числа $k\ge n_0$ и используйте это предположение для вывода $P(k+1)$.
- Индуктивное предположение является временным и условным: оно не предполагает истинность результата для всех целых чисел. Сделайте вывод, что $P(n)$ справедливо для всех целых чисел $n\ge n_0$, поскольку подтверждённый базовый случай и общая связь вместе охватывают их все.
Не допускайте случая $k+1$ во время попытки его доказать. Доказательство только $P(k+1)\Rightarrow P(k)$ даст неверную импликацию. Обратная алгебра может помочь в планировании, но доказательству требуется корректный прямой аргумент или обоснованная цепочка эквивалентных утверждений.
The two steps of proof by induction are the base case and the:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Induction needs a base case plus an inductive step from k to k+1.
For a claim stated for every positive integer n starting at 1, which base case is needed?
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
The base case checks the smallest value, usually n = 1.
If P(1) is true and P(k) implies P(k+1) for every integer k≥1, then P(n) is true for all positive integers n.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
The base case is explicitly1, and the forward implication applies to every later step. A proof starting at a different base has a different guaranteed range.
You can prove a result by induction using only the inductive step, without a base case.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Both steps are essential. Without the base case, the chain never starts.
Добавьте новый член в сумму
- Для конечной суммы отделите последний член суммы $k+1$. Замените только первые $k$ членов гипотезой, затем упростите выражение до формулы с индексом $n=k+1$.
- Покажите начальный случай, точное предположение и финальный вывод. Строка, которая лишь цитирует формулу суммы для $k+1$, не устанавливает необходимую связь.
Докажите $\sum_{r=1}^{n}r(r+1)=n(n+1)(n+2)/3$ для положительных целых чисел $n$.
При $n=1$ обе части равны $2$. Предположим, что формула верна для $n=k$. Тогда
Это требуемая формула $k+1$, поэтому результат следует для всех положительных целых чисел методом математической индукции.
Using induction, the sum 1 + 2 + ... + n = n(n+1)/2. For n = 10, find the sum.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
10(11)/2 = 55.
Prove by induction that $\sum_{r=1}^{n}(2r-1)^2=n(4n^2-1)/3$ for every positive integer $n$. Show the algebra in the forward step.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Prove by induction that $\sum_{r=0}^{n}3^r=(3^{n+1}-1)/2$ for every integer $n\ge0$. State the correct base case and explain the term count.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Доказать кратность делителю
- Чтобы доказать, что выражение делится на ненулевое целое число $m$, представьте его в виде произведения $m$ на целое число. На шаге индукции выделите предполагаемое делимое выражение и покажите, что каждый оставшийся член также является кратным $m$.
- Удобная кратная выражению $k$ и разность последовательных выражений могут помочь. Обозначьте множитель-целое; фраза «делится при беглом взгляде» может скрыть отсутствие использования гипотезы.
Пусть утверждение $F_n=10^n-4^n$ верно. При значении параметра $n=1$ выполняется равенство $F_1=6$. Предположим истинность утверждения $F_k=6q$ для некоторого целого числа $q$. Тогда
Выражение в скобках является целым числом. Следовательно, $6$ делит $F_{k+1}$, а метод математической индукции доказывает результат для каждого положительного целого числа $n$.
Prove by induction that $25^n+7^n-2$ is divisible by $6$ for every positive integer $n$. Identify an integer multiple in the step instead of quoting a pattern from small cases.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Prove by induction that $n^3-n$ is divisible by $6$ for every positive integer $n$. Explain why the extra term in the step is divisible by $6$, rather than only by $3$.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Использовать рекуррентную связь для перехода вперед
- Рекуррентное соотношение устанавливает корректный переход от $u_k$ к $u_{k+1}$. Убедитесь, что предлагаемая замкнутая формула имеет верное первое слагаемое, подставьте её $k$-версию в рекуррентное соотношение и упростите.
- Не подставляйте предложенную формулу $k+1$ в рекуррентную связь и не называйте это доказательством, если не установили обратимую эквивалентность с известной формулой $k$. Наиболее понятный путь начинается с данной рекуррентной связи.
Предположим $u_1=2$ и $u_{n+1}=3u_n+2$. Утверждение гласит: $u_n=3^n-1$. Оно верно при $n=1$. Приняв $u_k=3^k-1$,
Это доказывает предполагаемую замкнутую форму для всех положительных целых чисел, а не только для первых вычисленных членов $2,8,26$.
A sequence has $u_1=3$ и $u_{n+1}=2u_n+3$. Calculate its first four terms, conjecture a closed formula, and prove it by induction. Separate evidence for the guess from its proof.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Сохранить оценку и проверить знаки знаменателя
- Для неравенства, связанного с рекуррентной связью, подставьте гипотезу в выражение, знак которого можно контролировать. Объясните, почему его знаменатель положителен, прежде чем использовать его для сохранения неравенства.
- Иногда необходимая гипотеза содержит две оценки. Докажите, что обе сохраняются на шаге. Как только оценка установлена для каждого члена, она может обосновать более позднее рассуждение о монотонности без предположения ответа.
Пусть $u_1=1$ и $u_{n+1}=(4u_n+3)/(u_n+2)$. Докажите $0<u_n<3$.
Первый член удовлетворяет обоим неравенствам. Если $0<u_k<3$, то числитель и знаменатель $u_{k+1}$ положительны. Также,
Следовательно, $0<u_{k+1}<3$. По индукции, $0<u_n<3$ для каждого положительного целого числа $n$. Установленные оценки затем дают
так что последовательность возрастает. Последнее утверждение использует доказанную оценку; оно не заменяет это доказательство.
Suppose $0<u_1<1$ is given and $u_{n+1}=2u_n/(1+u_n)$. Prove by induction that $0<u_n<1$ for all positive integers. Then use your proved bounds to decide whether the sequence is increasing.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Доказать формулу для степени матрицы умножением
- Для степеней одной матрицы $M^{k+1}=M^kM$. Подставьте предполагаемое выражение для $M^k$, перемножьте строку на столбец и покажите, что каждый элемент имеет форму $k+1$.
- Степень матрицы не вычисляется возведением каждого элемента в степень. Кроме того, формула, проверенная при $M$ и $M^2$, является лишь доказательством до момента доказательства произвольного шага $k$.
Для $M=\begin{pmatrix}2&1\\0&1\end{pmatrix}$ утверждение
Случай $n=1$ представляет собой саму $M$. Используя предположение о $k$,
Следовательно, формула справедлива для всех положительных целых чисел методом математической индукции. Отдельный случай $n=0$ равен $M^0=I$, который также соответствует этой формуле.
За $M=\begin{pmatrix}2&1\\0&2\end{pmatrix}$, calculate $M^2$, then prove $M^n=\begin{pmatrix}2^n&n2^{n-1}\\0&2^n\end{pmatrix}$ for every positive integer $n$. Show the off-diagonal multiplication explicitly.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Гипотеза и доказательство закономерности производных
- Гипотезой называется предположение, основанное на фактах, но не являющееся установленной теоремой. Вычислите несколько производных, найдите закономерность и сформулируйте её точно, указав начальное значение $n$.
- Для формулы производной порядка $n$ продифференцируйте предполагаемую производную порядка $k$ ещё раз. Верная закономерность требует реального дифференцирования и упрощения на индуктивном шаге.
Для $f(x)=xe^{2x}$ первые производные равны $e^{2x}(2x+1)$, $e^{2x}(4x+4)$ и $e^{2x}(8x+12)$. Гипотеза
Первая производная даёт базовый случай. Дифференцирование формулы для $k$ приводит к
что является требуемой производной порядка $k+1$. Следовательно, гипотеза верна для любого положительного целого числа $n$.
In mathematics, a conjecture is:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
A conjecture is an unproven statement based on evidence — you then try to prove it (often by induction).
За $f(x)=x^2e^x$, compute the first three derivatives and conjecture $f^{(n)}(x)$ for $n\ge1$. Prove the formula by induction for all real $x$.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
The values n²−n+41 at n=1,2,3 are 41,43,47, all prime. A student conjectures that the expression is prime for every positive integer n. Test n=41 and explain what the result says about limited trials and induction.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Соответствие порядка производной в утверждении
- Если предполагаемая формула относится к производной порядка $2n$, то увеличение $n$ на единицу увеличивает порядок производной на два. Индуктивный шаг требует двукратного дифференцирования. Подсчитайте порядок производной до начала алгебраических преобразований.
- Отслеживайте знак чередования и коэффициент, зависящий от $n$, отдельно. Утверждение об отдельных чётных порядках не автоматически является утверждением о любой производной.
Для $f(x)=x\sin x$ утверждение
При $n=1$ и $f''(x)=2\cos x-x\sin x$, как и требовалось. Дифференцирование предполагаемой формулы для $2k$ один раз даёт $(-1)^k\{x\cos x+(2k+1)\sin x\}$. Повторное дифференцирование приводит к
completing the step to derivative order $2(k+1)$. The formula therefore holds for all positive integers $n$ by induction.
Prove by induction that for $f(x)=x\sin x$, $f^{(2n-1)}(x)=(-1)^{n-1}\{x\cos x+(2n-1)\sin x\}$ for every positive integer $n$. How many differentiations does one induction step require?
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Превращение короткого примера в гипотезу факториала
- Факториалом называется $n!=1\cdot2\cdots n$ для положительного целого числа $n$, где $0!=1$. Некоторые частичные суммы могут указывать на сдвинутый факториал, но тогда эта закономерность должна сохраняться на общем шаге индукции.
- Тщательно вычислите первые члены и поищите простое выражение после прибавления или вычитания константы. Когда в задаче требуется метод индукции, представьте именно это доказательство, даже если доступен прямой метод телескопической суммы.
Для $S_n=\sum_{r=1}^{n}r\,r!$ первые суммы равны $1,5,23,119$. Прибавление $1$ предполагает $S_n=(n+1)!-1$.
При $n=1$ обе части равны $1$. Предположив формулу для $k$,
Таким образом, предположение справедливо для всех положительных целых чисел по индукции. Тождество $r\,r!=(r+1)!-r!$ также объясняет, почему суммы телескопируют, однако перечисление начальных значений само по себе не является доказательством.
Let $S_n=\sum_{r=1}^{n}(r^2+r+1)r!$. Compute $S_1,S_2,S_3$, compare $S_n+1$ with $(n+1)!$, conjecture a formula for $S_n$, and prove it by induction.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Начните с первого значения, которое охватывает утверждение
- Утверждение может начинаться с $n=4$ или другого указанного целого числа. Докажите начальный случай и предположите, что $k$ находится в допустимом диапазоне; не заменяйте неявно область определения всеми положительными целыми числами.
- Для $2^n\ge n^2$ при $n\ge4$ базовый случай составляет $16=16$. Предположив $2^k\ge k^2$ для $k\ge4$, мы получаем $2^{k+1}\ge2k^2\ge(k+1)^2$, поскольку $2k^2-(k+1)^2=(k-1)^2-2>0$ находится в этом диапазоне. Следовательно, индукция доказывает stated claim для всех целых чисел $n\ge4$.
Цепочка доказывает указанную область, начиная с 4. На самом деле n=3 не работает, так как 8 меньше 9; точка начала является частью утверждения.
Prove $3^n\ge n^2$ by induction for every integer $n\ge2$. Justify the comparison in your inductive step. Does this proof by itself cover $n=1$?
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Проверьте импликацию и заключение
- Убедитесь, что гипотеза используется для доказательства следующего случая в прямом направлении, при этом все выражения определены. Проверенный базовый случай и обратная импликация сами по себе не устанавливают утверждение для последующих целых чисел.
- Сопоставьте вывод со связью: $P(k)\Rightarrow P(k+1)$ достигает каждого последующего целого числа, тогда как связь от $k$ к $k+2$ охватывает только одну четность из одного базового случая. Для покрытия обеих четностей с помощью этой связи требуются два начальных случая.
Утверждения $P(n): n\le5$ дают предупреждение. $P(1)$ истинно, и $P(k+1)\Rightarrow P(k)$ истинно для положительных целых чисел, однако $P(6)$ ложно. Обратная импликация не может заменить требуемый прямой шаг.
Докажите правильный начальный случай, предположите произвольное допустимое k и установите прямой шаг. Соотнесите заключение с достигнутой областью; формула производной четного порядка требует двух дифференцирований на каждом шаге.
Using the formula for the sum of the first n integers, what is the sum when n = 8, and why is the inductive step not enough on its own?
The closed formula gives the sum directly. Induction still has to anchor that formula with a first true case.
What is the sum of the first 8 integers?
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
8 times 9 divided by 2 is 36. Other options — 55 (the lesson sum for n = 10); 8 (the value of n).
A proposed proof of n+1<n says: assume k+1<k; adding 1 gives k+2<k+1; therefore the result holds for every positive integer. Identify the error and explain why a valid conditional calculation is insufficient.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
Let P(n) be n≤7. A student checks P(1), proves P(k+1) implies P(k), and concludes P(n) for all positive integers. Show why this fails and identify a value of k where the required forward link fails.
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.
For P(n): n is odd, P(1) is true and P(k) implies P(k+2). What range does this chain cover? Why can it not establish the claim for all positive integers merely by calling the link an inductive step?
Check the stated first case, use the exact hypothesis in a valid forward step for arbitrary k in its domain, and conclude only the range the proof establishes.