Глава 1. Основы математической логики

ГЛАВА 1. ОСНОВЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

1.72. Простым числом называется такое целое число p > 1, которое имеет только два делителя: единицу и само число p. Целое число s > 1, не являющееся простым, называется составным [4, 12].

1. Выпишите первые десять простых чисел.
2. Методом «от противного» докажите, что существует бесконечно много простых чисел.

1.73. Запишите отрицание предиката P(n) = {натуральное число n является простым}.

1.74. Докажите, что существует бесконечно много простых чисел вида 8n + 7, n = 1, 2, . . .

1.75. Докажите, что существует бесконечно много простых чисел вида 10n + 9, n = 1, 2, . . .

Факториалы и гармонические числа

1.76. Факториалом целого положительного числа n называется произведение всех натуральных чисел до n включительно [21, 30]: n! = ∏_i=1ⁿ i (по определению полагают 0! = 1 и 1! = 1). Докажите, что ∑_i=1ⁿ i(i + 1)! = 1 − 1/(n + 1)!.

1.77. Гармоническое число H_n определяется как сумма обратных величин первых n последовательных натуральных чисел [20, 30]: H_n = ∑_i=1ⁿ 1/i. Методом математической индукции докажите следующие тождества с гармоническими числами для всех натуральных значений переменной n:

1. ∑_i=1ⁿ H_i = (n + 1)H_n − n;
2. ∑_i=1ⁿ iH_i = n(n + 1)/4 * (2H_n+1 − 1).

Дополнительные упражнения по гармоническим числам

1.78.^* Докажите тождества, приведённые в предыдущем упражнении, не привлекая метод математической индукции.

1.79. Докажите следующие неравенства для гармонических чисел [30]: 1 + n/2 ⩽ H_2n ⩽ 1 + n для всех n = 1, 2, . . .

1.80. Определите все значения n, при которых гармоническое число H_n является целым.

Последовательность Фибоначчи

1.81. Последовательность Фибоначчи F_n = 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . . для n = 1, 2, . . . определяется рекуррентным соотношением: F_n+2 = F_n + F_n+1 с начальными условиями F₁ = F₂ = 1 [16, 21]. Используя метод математической индукции, докажите следующие свойства чисел Фибоначчи для всех натуральных n:

1. ∑_i=1ⁿ F_i = F_n+2 − 1;
2. ∑_i=1ⁿ F_2i−1 = F_2n;
3. ∑_i=1ⁿ F_2i = F_2n+1 − 1;
4. F_3n — чётны, а F_3n+1 и F_3n+2 — нечётны.

Тождества чисел Фибоначчи

1.82. Докажите справедливость соотношения ∑_i=1ⁿ F_i² = F_nF_n+1 для всех натуральных чисел n.

1.83. Докажите, что для всех натуральных n выполняются тождества:

1. ∑_i=1ⁿ iF_i = nF_n+2 − F_n+3 + 2;
2. ∑_i=1ⁿ (n − i + 1)F_i = F_n+4 − n − 3.

1.84. Вычислите сумму F₁ − F₂ + F₃ − F₄ + . . . + (−1)ⁿ⁺¹F_n.

Числа Люка

1.85. Числа Люка определяются как L₀ = 2, L₁ = 1 и L_n = L_n−1 + L_n−2 для целых чисел n ⩾ 2 [21]. Выпишите первые десять чисел Люка.

1.86. Докажите формулу для суммы чисел Люка: ∑_k=0ⁿ L_k = L_n+2 − 1, n ⩾ 1.

Принцип полной индукции

1.87. Часто бывает удобнее воспользоваться эквивалентной формой принципа математической индукции [4, 70]. Вторая форма принципа математической индукции (Принцип полной индукции). Пусть P(n) — предикат, определённый для всех натуральных чисел n, и пусть выполняются следующие условия:

1. P(1) истинно,
2. для произвольного k из истинности P(i) для всех i ⩽ k следует истинность P(k + 1).

Тогда P(n) истинно при любом натуральном n. Сформулируйте принцип полной индукции с помощью кванторов.

1.88.^* Докажите эквивалентность первой и второй форм принципа математической индукции.

Задачи на доказательство

1.89. Задано вещественное число x такое, что x + 1/x — целое. Докажите, что xⁿ + 1/xⁿ тоже целое для всех натуральных n [74].

1.90. Докажите формулу сложения членов ряда Фибоначчи F_n+m = F_n−1F_m + F_nF_m+1 для всех натуральных n и m, n > 1.

1.91. Докажите, что выражение F_n² + F_n+1² тоже является числом Фибоначчи.

Формулы Бине и золотое сечение

1.92.^* Докажите, что явное выражение для чисел Фибоначчи F_n, где n = 1, 2, 3, . . ., даётся формулой [21] F_n = 1/√5 * ((1 + √5)/2)ⁿ − 1/√5 * ((1 − √5)/2)ⁿ, известной как формула Бине.

1.93. Докажите, что для всех целых положительных n = 2, 3, . . . выполняется равенство φⁿ = F_nφ + F_n−1, где φ = (1 + √5)/2 — золотое сечение.

Соотношения чисел Фибоначчи

1.94. Докажите, что выполняется соотношение F_2n−1F_2n+1 − F_2n² = 1 для n = 1, 2, 3, . . .

1.95. Докажите, что выполняется соотношение F_2n+1F_2n+2 − F_2nF_2n+3 = 1 для n = 1, 2, 3, . . .

1.96.^* Докажите тождество arctg(1/F_2n) = arctg(1/F_2n+1) + arctg(1/F_2n+2), n ⩾ 1.

Связь чисел Люка и Фибоначчи

1.97. Докажите, что числа Люка могут быть выражены через числа Фибоначчи L_n = F_n−1 + F_n+1, n ⩾ 2.

1.98. Представив рекуррентное соотношение для чисел Фибоначчи в виде F_n = F_n+2 − F_n+1, можно обобщить F_n на все целые значения n. Найдите выражение для чисел Фибоначчи с отрицательными индексами.

1.99. Представив рекуррентное соотношение для чисел Люка в виде L_n = L_n+2 − L_n+1, можно обобщить L_n на все целые значения n. Найдите выражение для чисел Люка с отрицательными индексами.

1.100.^* Докажите, что явное выражение для чисел Люка L_n, где n = 1, 2, 3, . . . , даётся формулой L_n = ((1 + √5)/2)ⁿ + ((1 − √5)/2)ⁿ.

Тождества для чисел Люка

1.101. Докажите следующие тождества для n = 1, 2, 3, . . . :

1. L_4n = L_2n² − 2;
2. L_4n+2 = L_2n+1² + 2.

1.102. Докажите следующие тождества, верные для n = 1, 2, 3, . . . :

1. L_n² = L_2n + 2(−1)ⁿ;
2. L_n³ = L_3n + 3(−1)ⁿL_n.

1.103. Докажите следующие тождества, верные для n = 1, 2, 3, . . . :

1. L_n⁴ = L_4n + 4(−1)ⁿL_2n + 6;
2. L_n⁵ = L_5n + 5(−1)ⁿL_3n + 10L_n.

Дополнительные тождества

1.104. Упростите выражение L_n−1L_m + L_nL_m+1 для натуральных значений n и m.

1.105. Докажите тождество для целых неотрицательных n и k, 0 ⩽ k ⩽ n: L_n−kL_n+k = L_2n + (−1)^n+kL_2k.

1.106. Докажите тождества для целых i:

1. L_6i = L_2i(L_4i − 1);
2. L_8i = L_2iL_6i − L_4i.

Связующие соотношения

1.107. Докажите следующее соотношение, связывающее числа Фибоначчи и числа Люка: F_n+k + (−1)^kF_n−k = F_nL_k, n, k = 1, 2, 3, . . . , n > k.

1.108. Докажите тождества, устанавливающие связь между числами Фибоначчи и числами Люка:

1. F_n² = (L_2n − 4(−1)ⁿ)/5, n = 1, 2, 3, . . . ;
2. F_n−1F_n+1 = (L_2n + (−1)ⁿ)/5, n = 2, 3, . . .

Обобщения и признаки делимости

1.109. Докажите тождества для всех целых n > 3:

1. F_n−2F_n+2 = 1/5(L_2n − 9(−1)ⁿ);
2. F_n−3F_n+3 = 1/5(L_2n + 16(−1)ⁿ).

1.110. Обобщив тождества из упражнений 1.108 и 1.109, выразите произведение чисел Фибоначчи F_n−kF_n+k для целых неотрицательных n и k, причём k ⩽ n − 1, через числа Люка.

1.111. Докажите тождество, верное для натуральных значений n: L_n−1L_n+1 − L_n² = 5(−1)ⁿ⁻¹.

1.112. Докажите признак делимости на 3: для того чтобы число N делилось на 3, необходимо и достаточно, чтобы сумма цифр его десятичной записи делилась на 3.

Признаки делимости и теоремы

1.113. Докажите признак делимости на 7: для того чтобы число N делилось на 7, необходимо и достаточно, чтобы сумма утроенного числа десятков и числа единиц его десятичной записи делилась на 7.

1.114. Докажите признак делимости на 9: для того чтобы число N делилось на 9, необходимо и достаточно, чтобы сумма цифр его десятичной записи делилась на 9.

1.115. Докажите признак делимости на 11: для того чтобы число N делилось на 11, необходимо и достаточно, чтобы разность между суммами цифр, стоящих в его десятичной записи на чётных и нечётных местах, делилась на 11.

1.116.^* Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, либо простое, либо может быть представлено в виде произведения простых чисел [12, 50]. Используя принцип математической индукции во второй форме, докажите основную теорему арифметики.

1.117. Докажите, что для произвольного числа n в натуральном ряду 1, 2, 3, . . . найдутся n последовательных составных чисел.

1.118. Найдите десять последовательных составных чисел.