Приложение 10. Пример доказательства по индукции

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

Например, «сумма» всего лишь одного первого натурального числа 1 равна 1; сумма двух первых натуральных чисел 1+2 равна 3, сумма первых трех натуральных чисел 1+2+3 равна 6, сумма первых четырех натуральных чисел 1+2+3+4 равна 10 и т. д.

Возможно, что требуемая формула имеет вид

?(n) = ?·n(n + 1).

Иначе говоря, если требуется найти сумму n первых натуральных чисел, то нужно просто подставить число n в приведенную выше формулу и получить ответ.

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

?(1) = ?·1·(1 + 1).

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

?(n) = ?·n(n + 1).

то

?(n + 1) = ?(n) + (n + 1) = ?·n(n + 1) + (n + 1).

После преобразования членов в правой части получаем

?(n + 1) = ?·(n + 1)[(n + 1) + 1].

Важно отметить, что последняя формула «устроена» точно так же, как исходная формула с той лишь разницей, что там, где в исходной формуле стоит n, в новой формуле стоит n+1. Иначе говоря, если формула верна для n, то она должна быть верна и для n+1. Доказательство по индукции завершено.

Указания для дальнейшего чтения

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

ГЛАВА 1

1 Bell Е. Т. The Last Problem. — Mathematical Association of America, 1990.

История классического периода поисков доказательства Великой теоремы Ферма в популярном изложении.

2 Ralph L. Pythagoras — A Short Account of His Life and Philosophy. — Krikos, 1961.

3 German P. Pythagoras — A Life. — Routledge and Paul Kegan, 1979.

4 Heath Th. A History of Greek Mathematics. Vol. 1, 2. — Dover, 1981.

5 Gardner M. Mathematical Magic Show. — Knopf, 1977.

Сборник математических задач-головоломок по материалам раздела «Математические игры» журнала «Scientific American».

6 Stollum H.-H. River meandering as a self-organization process // Science, 1996. Vol. 271, P. 1710–1713.

ГЛАВА 2

1 Mahoney M. The Mathematical Career of Pierre de Fermat. — Princeton University Press, 1994.

Подробное исследование, посвященное жизни и деятельности Пьера де Ферма.

2 Huffman P. Archimedes' Revenge. — Penguin, 1988.

Увлекательные рассказы о радостях и горестях математики.

ГЛАВА 3

1 Bell Е. Т. Men of Mathematics. — Simon and Schuster, 1937.

Биографии величайших гениев в истории математики: Эйлера, Ферма, Гаусса, Коши и Куммера.

2 Lloyd M., Dybas H. S. The periodical cicada problem // Evolution, 1966. Vol. 20, P. 466–505.

3 Osen L. M. Women in Mathematics. — MIT Press, 1994.

В основном, это нематематический текст с биографиями многих выдающихся математиков-женщин, в том числе Софи Жермен.

4 Peri Т. Math Equals: Biographies of Women Mathematicians + Related Activities. — Addison-Wesley, 1978.

5 Mozans H.J. Women in Science. — D.Appleton and Co, 1913.

6 Dahan D. A. Sophie Germain // Scientific American, December 1991.

Краткая статья о жизни и трудах Софи Жермен.

7 Edwards H. M. Fermat's Last Theorem. A Genetic Introduction to Algebraic Number Theory. — Springer, 1977.

Математическое обсуждение Великой теоремы Ферма, включающее подробное изложение некоторых ранних попыток доказательства.

8 Burton D. Elementary Number Theory. — Allyn & Bacon, 1980.

Различные сообщения О. Коши Парижской академии наук. In: С. R. Acad. Sci., Paris, 1847. Vol. 24, P. 407–416, 469–483.

9 Lame G. Note au sujet de la demonstration du theoreme de Fermat // C. R. Acad. Sci., Paris, 1847. Vol. 24, P. 352.

10 Kummer Е. Е. Extrait d'une lettre de M. Kummer a M. Liouville // J. Math. Pures et Appl., 1847. Vol. 12, P. 136. Также см. Kummer Е. Е. Collected Papers. Vol. 1 (Ed. by A. Weil) — Springer, 1975.

11 Lines M. Е. A Number for Your Thoughts. — Adam Hilger, 1986.

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

ГЛАВА 4

1 Davis P. J., Chinn W. О. 3,1415 and All That. — Birkhauser, 1985.

Истории о математике и математиках, в том числе глава о Пауле Вольфскеле.

2 Wells D. The Penguin Dictionary of Curious and Interesting Numbers. — Penguin, 1986.

3 Wells D. The Penguin Dictionary of Curious and Interesting Puzzles. — Penguin, 1982.

4 Loyd S. Ju. Sam Loyd and his Puzzles. — Barse and Co, 1928.

5 Loyd S. Mathematical Puzzles of Sam Loyd. Ed. By Martin Gardner. — Dover, 1959.

6 Northropp Е. P. Riddles in Mathematics. — Van Nostrand, 1944.

7 Lodge D. The Picturgoers. — Penguin, 1993.

8 Ribenboim P. 13 Lectures on Fermat's Last Theorem. — Springer, 1980.

Обзор различных попыток доказательства Великой теоремы Ферма, написанный до работ Эндрю Уайлса. Рассчитан на аспирантов-математиков.

9 Devlin К. Mathematics: The Science of Patterns. — Scientific American Library, 1994.

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

10 Devlin К. Mathematics: The New Golden Age. — Penguin, 1990.

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

11 Stewart I. The Concepts of Modern Mathematics. — Penguin, 1995.

12 Russell В., Whitehead A. N. Principia Mathematica. 3 Vols. — Cambridge University Press, 1910–1913.

13 Kreisel G. Kurt Godel. In: Biographical Memoirs of the Fellows of the Royal Society, 1980.

14 Hardy G. H. A Mathematician's Apology. — Cambridge University Press, 1940.

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

15 Hodges A. Alan Turing: The Enigma of Intelligence. — Unwin Paperbacks, 1983.

Очерк жизни Алана Тьюринга, рассказывающий о его жизни; математическом творчестве и участии в раскрытии кода «Энигма».

ГЛАВА 5

1 Shimura G. Yutaka Taniyama and his time. — Bulletin of the London Mathematical Society, 1989. Vol. 21, P. 186–196.

Очерк жизни и творчества Ютаки Таниямы, написанный с весьма личной точки зрения.

2 Frey G. Links between stable elliptic curves and certain diophantine equations // Ann. Univ. Sarav. Math. Ser., 1986. Vol. 1, P. 1–40.