Как найти число возрастающих последовательностей

I am reproducing my algorithm from here, where its logic is explained:

dp[i, j] = same as before num[i] = how many subsequences that end with i (element, not index this time) 
         have a certain length

for i = 1 to n do   dp[i, 1] = 1

for p = 2 to k do // for each length this time   num = {0}

  for i = 2 to n do
    // note: dp[1, p > 1] = 0 

    // how many that end with the previous element
    // have length p - 1
    num[ array[i - 1] ] += dp[i - 1, p - 1] *1*   

    // append the current element to all those smaller than it
    // that end an increasing subsequence of length p - 1,
    // creating an increasing subsequence of length p
    for j = 1 to array[i] - 1 do *2*       
      dp[i, p] += num[j]

You can optimize *1* and *2* by using segment trees or binary indexed trees. These will be used to efficiently process the following operations on the num array:

• Given (x, v) add v to num[x] (relevant for *1*);
• Given x, find the sum num[1] + num[2] + ... + num[x] (relevant for *2*).

These are trivial problems for both data structures.

Note: This will have complexity O(n*k*log S), where S is the upper bound on the values in your array. This may or may not be good enough. To make it O(n*k*log n), you need to normalize the values of your array prior to running the above algorithm. Normalization means converting all of your array values into values lower than or equal to n. So this:

5235 223 1000 40 40

Becomes:

4 2 3 1 1

This can be accomplished with a sort (keep the original indexes).

Что имеется в виду под “подпоследовательностью”? Отрезкивида a[2], a[3], a[4]? Тогда решение предложенное zss, похоже на правду (в детали не лез). Или классическое (из матана) определение? Там a[1], a[3], a[7] тоже считается подпоследовательностью. Тогда все будет несколько посложнее.
Еще вопрос. Считать ли последовательность из одного элемента возрастающей подпоследовательностью? Ибо формально это так. Однако, постановщик задачи вправе их не учитывать, специально оговорив.

Добавлено через 42 секунды

Вот-вот. Именно это я и имел в виду.

Добавлено через 8 минут
zss, в преположении, что нас интересуют только отрезки длины больше 1, ваш код можно несколько упростить…

1
2
3

for(int i=0;i<N-1;i++) {
    if(A[i+1]>A[i]) amount ++;
}

Это O (nklogn) решение, где n – длина входного массива и k – размер возрастающих подпоследовательностей. Он основан на решение, упомянутое в вопросе.

vector<int> values, n length array, это массив, в котором будет выполняться поиск возрастающих подпоследовательностей.

vector<int> temp(n); // Array for sorting
map<int, int> mapIndex; // This will translate from the value in index to the 1-based count of values less than it

partial_sort_copy(values.cbegin(), values.cend(), temp.begin(), temp.end());

for(auto i = 0; i < n; ++i){
    mapIndex.insert(make_pair(temp[i], i + 1)); // insert will only allow each number to be added to the map the first time
}

mapIndex теперь содержит рейтинг всех чисел в values.

vector<vector<int>> binaryIndexTree(k, vector<int>(n)); // A 2D binary index tree with depth k
auto result = 0;

for(auto it = values.cbegin(); it != values.cend(); ++it){
    auto rank = mapIndex[*it];
    auto value = 1; // Number of sequences to be added to this rank and all subsequent ranks
    update(rank, value, binaryIndexTree[0]); // Populate the binary index tree for sub-sequences of length 1

    for(auto i = 1; i < k; ++i){ // Itterate over all sub-sequence lengths 2 - k
        value = getValue(rank - 1, binaryIndexTree[i - 1]); // Retrieve all possible shorter sub-sequences of lesser or equal rank
        update(rank, value, binaryIndexTree[i]); // Update the binary index tree for sub sequences of this length
    }
    result += value; // Add the possible sub-sequences of length k for this rank
}

После размещения всех n элементы values во все k размеры binaryIndexTree, values собраны в result представляют собой общее количество увеличивающихся подпоследовательностей длины k.

Для получения этого результата используются следующие функции дерева двоичных индексов:

void update(int rank, int increment, vector<int>& binaryIndexTree)
{
    while (rank < binaryIndexTree.size()) { // Increment the current rank and all higher ranks
        binaryIndexTree[rank - 1] += increment;
        rank += (rank & -rank);
    }
}

int getValue(int rank, const vector<int>& binaryIndexTree)
{
    auto result = 0;
    while (rank > 0) { // Search the current rank and all lower ranks
        result += binaryIndexTree[rank - 1]; // Sum any value found into result
        rank -= (rank & -rank);
    }
    return result;
}

Дерево бинарных индексов очевидно O (nklogn), но возможность его последовательного заполнения создает возможность использования в качестве решения.

mapIndex создает рейтинг для каждого числа в values, такое, что наименьшее число в values имеет ранг 1. (Например, если values равно “2, 3, 4, 3, 4, 1”, тогда mapIndex будет содержать: “{1, 1}, {2, 2}, {3, 3}, {4, 5}”. Обратите внимание, что «4» имеет рейтинг «5», потому что в values

binaryIndexTree и k разные деревья, уровень x будет представлять общее количество увеличивающихся подстрок, которые могут быть сформированы длиной x. Любое число в values может создать подстроку длиной 1, поэтому каждый элемент будет увеличивать свой ранг и все ранги над ним на 1.
На более высоких уровнях увеличивающаяся подстрока зависит от того, уже есть подстрока более короткой длины и более низкого ранга.

Поскольку элементы вставляются в дерево двоичных индексов в соответствии с их порядком в values, порядок появления в values сохраняется, поэтому, если элемент был вставлен в binaryIndexTree это потому, что он предшествовал текущему элементу в values.

Отличное описание того, как дерево бинарных индексов доступно здесь: http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

Вы можете найти исполняемую версию кода здесь: http://ideone.com/GdF0me

Числовая последовательность

Определение 1. Числовой последовательностью называется функция, аргументом которой является множество всех натуральных чисел, или множество первых n натуральных чисел.

Обозначается числовая последовательность так:

или

где −i-ый член последовательности.

Последовательности можно задавать тремя способами: словестно, аналитически и рекуррентно.

При словестном задании последовательности, описывается из каких элементов она состоит.

Последовательность нечетных чисел:

Последовательность простых чисел :

и т.д.

Последовательности (1) и (2) мы задали словестно.

Последовательность называется заданной аналитически, если указана формула ее n-го члена.

Последовательность нечетных чисел аналитически задается формулой

Действительно. Взяв для n значения 1, 2, 3, … мы получим последовательность (1).

Отметим, что последовательность простых чисел невозможно задать аналитически.

Последовательность задана рекуррентно, если указан метод вычисления n – го члена, при известных предыдущих членах последовательности.

Пример задания рекуррентной последовательности:

В этой последовательности

Определение 2. Числовая последовательность, в котором все члены равны называется стационарным.

Пример стационарной последовательности:

Возрастающие и убывающие последовательности

Определение 3. Последовательность, в которой каждый последующий член (кроме первого) больше предыдующего, называется возрастающей:

Определение 4. Последовательность, в которой каждый последующий член (кроме первого) меньше предыдующего, называется убывающей:

Возрастающие и убывающие последовательности называются также монотонными последовательностями.

Пример 1. Выяснить, монотонна ли последовательность

Решение. Запишем n+1 член последовательности (подставим вместо n, n+1):

Найдем разность членов и :

или

Так как n=1,2,3,… то правая часть уравнения (3) положительна. Тогда:

или

Таким образом, каждый последующий член последовательности больше предыдующего. Следовательно последовательность является возрастающим (и монотонным).

Пример 2. Выяснить, при каких значениях a последовательность (b_n) является возрастающей и при каких, убывающей:

Решение. Запишем n+1 член последовательности (вместо n подставим n+1):

Найдем разность членов и :

или

Посмотрим на правую часть выражения (4). Если a<10, то . Тогда последовательность является возрастающей. Если a>10, то . Тогда последовательность является убывающей. При a=10 . Последовательность имеет одинаковые члены:

т.е. имеем дело с последовательностью

Очевидно, что последовательность (5) не является монотонной. Она является стационарной последовательностью.

Ограниченные и неограниченные последовательности

Определение 5. Последовательность (y_n) называется ограниченной сверху, если существует такое число k, что y_n<k при любом n.

Определение 6. Последовательность (y_n) называется ограниченной снизу, если существует такое число k, что y_n>k при любом n.

Определение 7. Последовательность (y_n) называется ограниченной, если она ограничена и сверху, и снизу.

Пример 3. Показать, что последовательность (a_n) является монотоннной и ограниченной:

Решение. Запишем n+1 член последовательности (вместо n подставим n+1):

Найдем разность членов и :

или

Правая часть равенства (6) положительна при любых натуральных чисел n. Следовательно последовательно (a_n) возрастающая (и монотонная).

Далее, сделаем эквивалентное преобразование для проследовательности (5):

или

Из выражения (7) видно, что при любых n a_n≤1. Т.е. хотя последовательность возрастает, то остается меньше числа 1 (ограничена сверху). Запишем несколько членов данной последовательности, задав n=1,2,3,…

Так как последовательность возрастающая, то все члены последовательности не меньше . Тогда последовательность ограничена также и снизу. Таким образом последовательность ограничена и всерху, и снизу, т.е. является ограниченной последовательностью.

Сходящиеся и расходящиеся последовательности

Рассмотрим две числовые последовательности:

На координатной прямой изобразим члены этих последовательностей:

Как можно заметить из рисунков Рис.1 и Рис.2, члены последовательности , при увеличении n, постепенно приближаются к некоторой точке (в данном случае к точке O), а для последовательности такое не наблюдается. Говорят, что последовательность сходится, а полседовательность расходится.

Предел числовой последовательности

Точка, к которой приближаются члены последовательности при увеличении n, называется пределом последовательности. Для последовательности (10) пределом является число 0. Более строго предел последовательности определяется так:

Определение 8. Число k называют пределом последовательности (y_n), если для любой заранее выбранной окресности точки k, можно выбрать такой номер n₀, чтобы все члены последовательности, начиная с номера n₀ содержались в указанной окрестности.

Если k является пределом последовательности (y_n), то пишут ( стремится к k или сходится к k).

Обозначают это так:

Выраженние (11) читается так: предел проследовательности , при стремлении n к бесконечности равен k.

Изложим некоторые пояснения к определению 8.

Пусть выполнено (11). Возьмем окрестность точки k, т.е. интервал , где радиус этой окрестности ( >0). По определению, существует номер n₀, начиная с которого вся последовательность содержится в указанной окресности, т.е.

Если же взять другую окресность (пусть ), то найдется другой номер n₁, начиная с которого, вся последовательность содержится в указанной окрестности, но этот номер будет больше n₁ > n₀.

Пример 4. Дана полследовательность (y_n):

Доказать, что .

Решение. Найдем любую окрестность точки 0. Пусть ее радиус равен r. Тогда всегда можно выбирать n₀ так, чтобы .

Пусть, например, r=0.001. Вычислим n‘ из уравнения

Имеем:

В качестве n₀ берем 501. Имеем:

или

Запишем члены последовательности (12) начиная с номера 501:

Далее, учитывая (13), имеем:

Следовательно, все члены последовательности (12) начиная с номера 501 попадают в окресность . А по определению 8, это означает:

Пример 5. Дана полследовательность (y_n):

Доказать, что .

Решение. Найдем любую окрестность точки 2. Пусть ее радиус равен r. Тогда всегда можно выбирать n₀ так, чтобы

Рашим (15) относительно n₀:

Получили

Неравенство в (17) всегда выполняется так как n₀ натуральное число, а правая часть неравенства отрицательно (это означает, что для любого n₀). Из неравенства (16) можно найти номер n₀, начиная с которого члены последовательности попадают в окресность (2−r; 2+r). Например, пусть r=0.001, тогда . Тогда нужно брать n₀=2000. И тогда все члены последовательности, начиная с номера 2000 попадают в окрестность (2−r; 2+r).

Запишем члены последовательности, начиная с номера 2000:

Легко проверить, что . Тогда, учитывая, что данная последовательность возрастающая (см. пример 1), получим:

Пример 6. Найти предел последовательности

Решение. Выполним некоторые преобразования выражения (18):

Тогда последовательность (18) можно переписать так:

Как видно из (19), пройдя по членам последовательности слева направо, из числа 1 вычитается все меньшее и меньшее положительное число. Т.е. последовательность приближается к числу 1. Тогда 1 является пределом последовательности (19) и (18):

На Рис. 3 представлена функция . Абсцисы нарисованных точек это номера членов последовательности, а ординаты образуют последовательность (18) (или (19)). Прямая y=1 (горизонтальная пунктирная линия) называется горизонтальной асимптотой. Как видно из Рис.3 последовательность приближается к горизонтальной асимптоте.

Свойства сходящихся последовательностей

Сходящиеся последовательности обладают рядом свойств.

Свойство 1. Если последовательность сходится, то только к одному пределу.

Свойство 2. Если последовательность сходится, то она ограничена.

Свойство 3. Если последовательность монотонна и ограничена, то она сходится (теорема Вейерштрасса).

Предел стационарной последовательности равен значению любого члена последовательности:.

Теорема. Если , то

1. Предел суммы равен сумме пределов:

2. Предел произведения равен произведению пределов:

3. Предел частного равен частному пределов:

(при c≠0).

4. Постоянный множитель можно вывести за знак предела:

Пример 7. Найти предел последовательности:

Решение. Так как , то

Пример 8. Найти предел последовательности:

Решение. Применив правило “предел суммы” теоремы, получим

Пример 9. Вычислить:

Решение. Делим числитель и знаменатель дроби на наивысшую из имеющихся степень переменного n. Далее используем правило “предел суммы” для числителя и знаменателя и правило “предел частного”:

План урока:

Понятие числовой последовательности

Способы задания последовательностей

Возрастающие и убывающие последовательности

Ограниченные и неограниченные последовательности

Последовательности в жизни

Понятие числовой последовательности

Попытаемся записать в ряд все четные числа, начиная с двойки:

2, 4, 6, 8, 10, 12

Ясно, что запись можно продолжать бесконечно. Мы получили некоторый ряд чисел, в данном случае бесконечный. Любой такой ряд называется бесконечной числовой последовательностью

Приведем примеры бесконечных числовых послед-тей:

Заметим, что числа в послед-ти могут повторяться. Так, известно, что число π – это бесконечная десятичная дробь 3,1415926… Выписывая в ряд эти цифры, можно получить послед-ть, в которой будут повторяющиеся числа:

3, 1, 4, 1, 5, 9, 2, 6

Числа, входящие в состав послед-ти, называют членами послед-ти. Всегда можно указать, какое число является первым членом послед-ти, какое – вторым и т. д. Для их обозначения используются буквы с индексами. Например, есть послед-ть четных чисел 2, 4, 6, 8… Выпишем первые ее члены, обозначая их буквой а:

Получается, что каждому натуральному числу n соответствует какой-то единственный член послед-ти, который обозначается как а_n. То есть послед-ть задает некое правило, с помощью которого для каждого числа n можно вычислить число a_n. Отсюда можно сформулировать более сложное определение бесконечной числовой послед-ти – это функция, областью определения которой является множество натуральных чисел.

Способы задания последовательностей

Чтобы задать послед-ть, необходимо указать способ, с помощью которого можно вычислить любой ее член. Проще всего это сделать, записав формулу, в которой в качестве переменной использует номер члена послед-ти n.Такая формула называется формулой n-ого члена последовательности.

Пример. Послед-ть задается формулой а_n = 3n. Выпишите первые пять членов этой послед-ти.

Решение. Чтобы найти первый член послед-ти, то есть а₁, просто подставим в формулу единицу:

Аналогично можно вычислить и следующие четыре члена послед-ти:

Итак, послед-ть имеет вид:

3, 6, 9, 12, 15…

Ответ: 3, 6, 9, 12, 15

Пример:Запишите формулу n-ого члена для послед-ти

1, 3, 5, 7, 9…

состоящей из положительных нечетных чисел.

Решение. Каждое нечетное число можно представить в виде 2n– 1. Тогда получаем:

Получаются как раз члены послед-ти, указанной в условии. Поэтому формула n-ого члена будет выглядеть как а_n = 2n– 1.

Ответ: а_n = 2n– 1.

Стоит обратить внимание, что для вычисления n-ого члена послед-ти НЕ нужно вычислять все предшествующие члены.

Пример. Запишите 38-й член послед-ти, заданной формулой а_n = 2n² + 1.

Решение. Подставим n = 38 в формулу и получим:

Ответ: 1445

Теперь рассмотрим послед-ть, в которой первые два числа равны единице, а каждый следующий член равен сумме двух предыдущих. Она называется последовательностью Фибоначчи и начинается так:

1, 1, 2, 3, 5, 8, 13, 21…

Действительно, по условию, первые два члена – это единица:

а каждый следующий равен сумме предыдущих:

Формулу n-ого члена записать для послед-ти Фибоначчи очень сложно (хотя и возможно). Вместо этого здесь удобнее использовать рекуррентный способ задания последовательности. Записываются первые несколько членов послед-ти, а после дается формула (ее называют рекуррентной), которая позволяет вычислить следующие члены по предыдущим:

При использовании рекуррентного способа для вычисления n-ого члена обычно необходимо вычислить все предыдущие члены послед-ти.

Пример. Найдите пятый член послед-ти, заданной рекуррентной формулой а_n= 3•а_n–1– 1, если а₁ = 2.

Решение. Будем последовательно вычислять все члены послед-ти, вплоть до пятого:

Ответ: 5

Надо понимать, что одну и ту же послед-ть можно задать по-разному. Так, послед-ть четных чисел можно задать формулой n-ого члена а_n = 2n, так и рекуррентной формулой а_n = a_n–1 + 2, если а₁ = 1.

Пример. Дана послед-ть, заданная формулой а_n = n². Задайте ее рекуррентным способом.

Решение. Сначала вычислим первый член послед-ти:

Чтобы записать рекуррентную формулу, попытаемся найти разницу между членами, имеющими номера n и (n– 1):

Итак, получили равенство

Перенесем в нем слагаемое (– a_{n– 1}) вправо и получим рекуррентную формулу:

Наконец, некоторые послед-тине получается задать ни формулой n-ого члена, ни рекуррентным способом. Их можно только описать. Таковой является, например, послед-ть простых чисел:

2, 3, 5, 7, 11…

Мы не будем это доказывать, однако не существует такой формулы, которая позволяла бы вычислить n-ое простое число либо по самому числу n, либо по предыдущим простым числам. Действительно, для построения такой послед-ти используют особый алгоритм, известный как решето Эратосфена. Если бы существовала формула n-ого члена, то потребность в использовании решета Эратосфена отпала бы.

Возрастающие и убывающие последовательности

Рассмотрим послед-ть, заданную формулой а_n = 5n:

5, 10, 15, 20, 25…

Очевидно, что каждый следующий член больше предыдущего. Это значит, что мы имеем дело с возрастающей последовательностью.

Теперь изучим послед-ть, заданной рекурсивным способом:

Выглядеть он будет так:

50, 48, 46, 44, 42…

Ясно, что каждый следующий член послед-ти меньше предыдущего. Такой ряд чисел называется убывающей последовательностью.

Убывающие и возрастающие послед-ти называют также монотонными последовательностями.

Для того, чтобы определить характер послед-ти, достаточно найти разность членов а_nи а_n+1. Если получается положительное выражение, то послед-ть возрастает, а если выражение отрицательно, то послед-ть убывает. Если получилось выражение, которое может иметь различный знак, то послед-ть вовсе не является монотонной.

Пример. Послед-ть задана формулой a_n = n/(n + 1). Является ли она убывающей либо возрастающей?

Решение. Запишем выражения для вычисления n-ого и (n+ 1)-ого члена послед-ти:

Осталось найти их разницу:

При натуральных значениях n полученная разница является положительным числом. Это значит, что каждый следующий член больше предыдущего, то есть послед-ть является возрастающей.

Ответ: возрастающая.

Пример. Исследуйте на монотонность послед-ть, заданную формулой

Решение. Если выписать первые члены послед-ти, может показаться, что она – убывающая:

-7, -12, -15, -16…

Но это не так. Запишем выражения для n-ого и (n + 1)-ого члена послед-ти:

Теперь найдем их разность:

Получили выражение (2n– 7), которое может быть как отрицательным, так и положительным (при n≥ 4). Это значит, что послед-ть немонотонна. В этом можно убедиться, вычислив четвертый и пятый член послед-ти:

Получаем, что у₅>у₄, поэтому послед-ть не является убывающей

Ответ: послед-ть немонотонна.

 Ограниченные и неограниченные последовательности

Изучим послед-ть, заданную с помощью формулы b_n = 1/n. Её первые члены будут выглядеть так:

Очевидно, что она является убывающей, ведь каждая следующая дробь меньше предыдущей. Вместе с тем все члены послед-ти являются положительными числами. Это значит, что для каждого n выполняется неравенство b_n> 0. То есть последовательность ограничена числом 0. В математике такие послед-ти называют ограниченными снизу.

Существует и послед-ти, ограниченные сверху. Это такие послед-ти, каждый член которых меньше какого-то постоянного числа.

В качестве примера можно привести послед-ть, заданную формулой с_n = 1 – 1/n. Каждый следующий ее член все ближе к единице, но ни один из них не достигает ее. Покажем, как строго доказать это. Для этого используют метод рассуждений «от противного».

Предположим, что послед-ть с_n = 1 – 1/n не ограничена числом 1 сверху. Тогда существует такой ее член с_n, для которого выполняется условие

Попытаемся найти номер этого члена:

Полученное нер-во выполняется только для отрицательных n. Но n – это натуральное, то есть положительное число. Это говорит о том, что не существует такого натурального n, для которого справедливо нер-во 0 ≥ 1/n. Значит, и не существует такого с_n, для которого верно нер-во с_n ≥ 1. Из этого следует, что послед-ть ограничена сверху числом 1.

Пример. Докажите, что послед-ть m_n = n² – 6n + 4 ограничена снизу числом (– 6).

Решение. Предположим, что на самом деле послед-ть не ограничена снизу числом (– 6). Тогда хотя бы для одного ее члена будет выполняться нер-во

Найдем номер этого члена:

Получили неравенство второй степени. Для его решения следует найти корни квадратного трехчлена. Начнем с вычисления дискриминанта:

Дискриминант отрицательный, а ветви параболы смотрят вверх. Поэтому схематично парабола относительно оси Ох будет располагаться так:

Видно, что нер-во решений не имеет. Значит, не существует такого номера n, для которого верно условие m_n ≤ – 6. Следовательно, послед-ть ограничена снизу числом (– 6).

Если послед-ть ограничена одновременно и снизу, и сверху, то ее называют просто ограниченной послед-тью.

Примером ограниченной последовательности является b_n = 1/n. С одной стороны, она ограничена нулем снизу. С другой стороны, она ограничена сверху числом 2, так как первый ее член равен единице, а вся послед-ть – убывающая.

Примером неограниченной последовательности является v_n = 5n, ведь ее невозможно ограничить сверху.

Примером ограниченной последовательности является b_n = 1/n. С одной стороны, она ограничена нулем снизу. С другой стороны, она ограничена сверху числом 2, так как первый ее член равен единице, а вся послед-ть – убывающая.

Примером неограниченной последовательности является v_n = 5n, ведь ее невозможно ограничить сверху.

1, 3, 5, 7, 9…

Начнем вычислять сумму первых n членов двумя способами: просто складывая и используя формулу S_n= n². Посмотрим, будут ли получаться одинаковые результаты.

Видно, что формула работает. Однако, сколько бы раз мы не проверяли ее, это не будет служить строгим доказательством ее справедливости. Возможно, что она будет работать для первого миллиона члена послед-ти, а для 1000001-ого даст ошибку. Поэтому поступим иначе. Предположим, что фор-ла S_n= n² верна хотя бы для одного значения n, равного k:

Докажем, что тогда она будет верна и для следующего числа k + 1. То есть нужно доказать равенство

Ясно, что сумму (k + 1) членов послед-ти можно получить, прибавив к сумме k членов (то есть к S_k )ещё одно слагаемое a_n+1, то есть справедлива запись:

При этом мы предположили, что верно равенство

а число a_n+1 можно посчитать по формуле n-ого члена:

Тогда можно записать

Получили формулу сокращенного умножения – квадрат суммы. Его можно «свернуть»:

Итак, если для формула S_k= k² верна для k = 1 (а в этом мы убедились в самом начале), то она верна и для k = 2. Но если она верна для k = 2, то она верна и для k = 3 и т.д. Получаем цепочку утверждений, каждое из которых подтверждает истинность формулы для конкретного натурального числа k, а все вместе они подтверждают ее истинность для всех натуральных чисел. Таким образом, нам удалось доказать справедливость формулы S_n= n².

Сформулируем принцип математической индукции:

То есть сначала надо доказать, что утверждение выполняется при n = 1. Это действие называют шагом индукции. Далее предполагают, что утверждение верно при n = k, и из этого выводят, что оно верно и для n =k + 1.

Пример. Докажите с помощью математической индукции, что сумма квадратов первых n натуральных чисел вычисляется по формуле:

Решение. Докажем базис индукции, то есть то, что утверждение верно при n = 1. Действительно, подставив единицу в формулу, получим:

Получили один и тот же результат. Базис индукции доказан.

Теперь предположим, что формула верна для произвольного n = k:

Тогда сумма (k + 1) квадратов может быть найдена по формуле

Подставим в нее выражение для S_k и получим:

С другой стороны, нам надо доказать, что величина S_k+1определяется по формуле

Приравняем выражения (1) и (2) и покажем, что они тождественно равны:

Умножим обе части на 6 и получим:

Получили одинаковые выражения в обоих частях рав-ва, поэтому оно является верным при любом значении k. Значит, мы смогли доказать шаг индукции, и следовательно, всё исходное утверждение.

Пример. Докажите, что любую сумму, большую 7 копеек, можно оплатить, используя только два типа монет: по 3 и 5 копеек.

Это утверждение, очевидно, верно сумм в 8, 9 и 10 копеек:

Добавив к этим суммам ещё одну трехкопеечную монету, мы сможем получить выражения для следующих трех чисел:

С помощью ещё одной монетки в три копейки можно уплатить следующие 3 суммы:

Ясно, что продолжая подобные рассуждения, можно для любого натурального числа записать эквивалентную ему сумму пятерок и троек, что доказывает утверждение из условия.

Последовательности в жизни

Порою, изучая математические объекты, люди задумываются – а какое отношение все эти формулы имеют к реальной жизни? Встречаются ли последовательности в природе и обществе, или они являются лишь плодом фантазии математиков?

На самом деле последовательности имеют большое практическое приложение. Так, Фибоначчи сформулировал свою последовательность тогда, когда изучал скорость размножения кроликов. Если каждая пара кроликов рожает в месяц ещё одну пару, а через месяц и старая, и новая пара рожает ещё кроликов, то их численность будет расти также, как и последовательность Фибоначчи! Аналогично протекают процессы роста популяций других животных.

Большое значение последовательности имеют в программировании. Дело в том, что порою программам нужно получить некоторое случайное число, чтобы имитировать случайные события. Однако по ряду причин компьютеру тяжело сгенерировать истинно случайное число, поэтому часто используют генераторы псевдослучайных чисел. Это особые алгоритмы, порождающие последовательности чисел, которые кажутся случайными, хотя таковыми на самом деле не являются.

Встречаются последовательности и в астрономии. В частности, расстояние от планет до Солнца примерно можно рассчитать с помощью особой последовательности Тициуса-Боде. Последние исследования показывают, что и расположение планет в других планетных системах хорошо описывается этой последовательностью.