Решим данное рекуррентное соотношение.
A(m1,m2,…,mn)= 
Докажем методом математической индукции по числу n.
1) База: n=1 A(m1)=20∙m1=m1 (верно);
2) Индуктивный переход: пусть верно для всех чисел t≤(n−1). Докажем для t=n:
=2∙( 
) 
=
Из 1 и 2 следует, что A(m1,m2,…,mn)=
при n > 0.
Задача 13.На какое максимально возможное число областей плоскость делится nзигзагообразными линиями, каждая из которых состоит из двух параллельных полубесконечных прямых, соединенных прямолинейным отрезком?
Решение. Пусть 
- это максимальное число областей, на которые плоскость делится n зигзагообразными линиями. Рассмотрим частные случаи: 
(Здесь Ln =
+ 1- максимальное число областей, на которые плоскость делится n прямыми) 
Из этих частных случаев можно видеть, что зигзагообразная линия подобна трем прямым с тем лишь отличием, что области сливаются, если «три» прямые не продолжать после их пересечения:Области 1, 2, 6 и 3, 4, 5, которые были бы разделены при наличии трех прямых, превращаются в единую область в случае одной зигзагообразной линии, т.е. мы теряем четыре области. Так же у нас имеется две параллельные прямые, следовательно, мы теряем еще одну область. Таким образом, если привести все в надлежащий порядок, то все зигзагообразные линии должны пересекаться между собой и точки изломов должны лежать «по ту сторону» пересечений с другими линиями, и мы теряем только пять областей на одну линию. Таким образом,
.Данную задачу можно решить и по другому, если заметить, что зигзаг можно рассматривать как «прямую», и отрезок, соединяющий две полупрямые, может быть сколь угодно длинным. Тогда данная задача аналогична задаче о нахождении максимального числа Ln областей, на которые плоскость делится n прямыми (две прямые имеют одну точку пересечения). В нашем случае две зигзагообразные линии имеют девять точек пересечения.
С другой стороны, две зигзагообразные линии подобны шести прямым с тем лишь отличием, что области сливаются, если «шесть» прямых не продолжать после их пересечения,Эти шесть прямых образуют 20 областей, следовательно, при пересечении двух зигзагообразных линий мы теряем восемь областей.
Таким образом, получаем рекуррентное соотношение:
Решим данное соотношение.
+9n−−8=
+9∙(n−1)−8+9n−8=
=
при n ≥ 0.Докажем полученное равенство методом математической индукции.
1) База: n=0,
(верно);2) Индуктивный переход: пусть верно для всех чисел t≤ (n–1). Докажем для t=n:
= 
+9n−7= .Из пунктов 1 и 2 следует: при n> 0
.Задача 14.На какое максимальное число частей можно разделить головку сыра с помощью пяти плоских разрезов? (Головка сыра должна оставаться в исходном положении, пока вы ее режете, и каждому разрезу должна соответствовать некоторая плоскость в трехмерном пространстве.) Найдите рекуррентное соотношение для Рn - максимального числа трехмерных областей, на которое может быть разбито пространство n произвольно расположенными плоскостями.
Решение. Сначала найдем рекуррентное соотношение для Рn, а потом с помощью этого соотношения определим, на сколько частей можно разделить головку сыра с помощью пяти плоских разрезов (головка сыра является ограниченным пространством).
Итак, рассмотрим частные случаи: Р1=2, Р2=4, Р3=4+4=8, Р4=8+7=15. Эксперимент показывает, что данная задача аналогична задаче о нахождении максимального числа Ln областей, на которые плоскость делится n прямыми (Ln=Ln-1+n), но только с тем отличием, что дело обстоит в пространстве. Две произвольные плоскости пересекаются по единственной прямой, и для того, чтобы получить максимальное число трехмерных областей надо, чтобы каждая новая проведенная плоскость не была параллельна никакой другой плоскости (следовательно, она пересекает каждую из них), и не проходила ни через одну из имеющихся прямых пересечения (следовательно, она пересекает каждую из плоскостей по различным прямым). Таким образом, проводя новую n-ую плоскость, мы к старым
областям добавляем столько трехмерных областей, сколько образуется областей на n-ой плоскости образованных 
прямой пересечения этой плоскости со всеми остальными плоскостями. Поэтому рекуррентное соотношение имеет вид: 
Следовательно, головку сыра можно разделить с помощью пяти плоских разрезов не более чем на 26 частей.
Задача 15.У Иосифа был друг, которого он спас, поставив на предпоследнее спасительное место. Чему равен F(n) - номер предпоследнего выжившего, если экзекуции подлежит каждый второй?
Решение. Допустим, что первоначально имеется 2n людей. После первого обхода мы остаемся с номерами: 1, 3, 5, 7, …, 2n−3, 2n−1. Следующий обход будет начинаться с номера 3. Это то же самое, если бы мы начинали с n людей, за исключением того, что номер каждого уцелевшего удваивается и уменьшается на 1. Тем самым
, следовательно 
, то, подставляя данное равенство в соотношение (*) получим рекуррентное соотношение: 
