Рекурсивные последовательности

Эта тема является частью раздела текстовых задач в Quant GMAT Focus.

В предыдущих разделах мы рассматривали последовательности, где каждый член aₙ задается явной алгебраической формулой через n.
В таких случаях:

• можно подставить любое значение n;
  
  
• и сразу найти нужный член (например, 40-й или 80-й).
  
  

К таким последовательностям относятся:

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

Новый тип последовательностей

Теперь рассмотрим совершенно другой способ задания последовательностей — рекурсивный.

Чтобы понять идею, начнем с одного из самых известных примеров в истории математики — последовательности Фибоначчи.

Пример: последовательность Фибоначчи

Последовательность выглядит так:
1, 1, 2, 3, 5, 8, …

На первый взгляд закономерность неочевидна.
Однако правило следующее:

• первые два числа равны 1 (их будем называть начальными значениями или seed values);
  
  
• каждый следующий член равен сумме двух предыдущих.
  
  

Важно:

• термин seed values используется не во всех учебниках, но в этом разделе мы будем применять именно его;
  
  
• GMAT не требует, чтобы вы самостоятельно угадывали такие закономерности по списку чисел;
  
  
• на тесте правило всегда будет задано явно.
  
  

Что значит «рекурсивно»

Обозначим:

• aₙ — n-й член последовательности;
  
  
• aₙ₋₁ — предыдущий член;
  
  
• aₙ₋₂ — член перед предыдущим.
  
  

Если aₙ определяется через предыдущие члены, то такое задание называется рекурсивным, а последовательность — рекурсивной.

Иными словами:

В рекурсивной последовательности каждый новый член вычисляется на основе одного или нескольких предыдущих.

Что обязательно дается на тесте

Для любой рекурсивной последовательности GMAT всегда укажет:

1. начальные значения (обычно a₁ или a₁ и a₂);
   
   
2. формулу, связывающую aₙ с предыдущими членами.
   
   

Без этих данных задача была бы нерешаемой.

Пример 1: рекурсия через один предыдущий член

Пусть:

• a₁ = 1
  
  
• aₙ = 2aₙ₋₁ + 1
  
  

Найдем первые несколько членов:

• a₁ = 1
  
  
• a₂ = 2 · 1 + 1 = 3
  
  
• a₃ = 2 · 3 + 1 = 7
  
  
• a₄ = 2 · 7 + 1 = 15
  
  
• a₅ = 2 · 15 + 1 = 31
  
  

Ключевое отличие от предыдущих типов последовательностей:

• невозможно сразу перейти к, например, a₅;
  
  
• нужно последовательно вычислять каждый член, начиная с начального.
  
  

Именно поэтому:

• GMAT никогда не попросит найти 40-й или 80-й член рекурсивной последовательности;
  
  
• вопросы ограничиваются 5–6 шагами вычислений.
  
  

Пример 2: практика с вычислением

Дана рекурсивная последовательность:

• a₁ = 1
  
  
• aₙ = (aₙ₋₁ − 1)² + 3
  
  

Найти a₄.

Решение по шагам:

• a₁ = 1
  
  
• a₂ = (1 − 1)² + 3 = 0 + 3 = 3
  
  
• a₃ = (3 − 1)² + 3 = 2² + 3 = 7
  
  
• a₄ = (7 − 1)² + 3 = 6² + 3 = 39
  
  

Ответ: 39.

Рекурсия через два предыдущих члена

В более сложных задачах aₙ может зависеть от двух предыдущих членов:

• aₙ₋₁;
  
  
• aₙ₋₂.
  
  

Последовательность Фибоначчи — классический пример:

• a₁ = 1
  
  
• a₂ = 1
  
  
• aₙ = aₙ₋₁ + aₙ₋₂
  
  

Это алгебраическая запись правила:

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

Пример 3: «фибоначчиподобная» последовательность

Даны начальные значения:

• a₁ = 1
  
  
• a₂ = 3
  
  
• aₙ = aₙ₋₁ + aₙ₋₂
  
  

Найти a₆.

Решение:

• a₃ = 1 + 3 = 4
  
  
• a₄ = 3 + 4 = 7
  
  
• a₅ = 4 + 7 = 11
  
  
• a₆ = 7 + 11 = 18
  
  

Ответ: 18.

Пример 4: сложная рекурсивная формула

Дана последовательность:

• S₁ = 2
  
  
• S₂ = 3
  
  
• Sₙ = (Sₙ₋₁ − 1) · Sₙ₋₂ для n > 2
  
  

Найти S₆.

Решение по шагам:

• S₁ = 2
  
  
• S₂ = 3
  
  

Третий член:

• S₃ = (3 − 1) · 2 = 2 · 2 = 4
  
  

Четвертый член:

• S₄ = (4 − 1) · 3 = 3 · 3 = 9
  
  

Пятый член:

• S₅ = (9 − 1) · 4 = 8 · 4 = 32
  
  

Шестой член:

• S₆ = (32 − 1) · 9 = 31 · 9
  
  
• 31 · 9 = 279
  
  

Ответ: 279.

Итог

• В рекурсивной последовательности каждый член определяется через один или два предыдущих.
  
  
• Начальные значения всегда заданы явно.
  
  
• Формулы обычно имеют вид:
  
  
  • aₙ = f(aₙ₋₁)
    
    
  • или aₙ = f(aₙ₋₁, aₙ₋₂)
    
    
• Нельзя перескочить сразу к нужному члену.
  
  
• Нужно вычислять каждый член по порядку, начиная с начальных значений.
  
  
• На GMAT задачи ограничиваются небольшим числом шагов, чтобы расчеты оставались управляемыми.
  
  

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

Далее изучим инклюзивный подсчет.