Приложение 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. — Birkhäuser, 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 Gödel. 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.
Статья, сыгравшая решающую роль, в которой Фрей высказал предположение о существовании связи между гипотезой Таниямы-Шимуры и Великой теоремы Ферма.
ГЛАВА 6
1 Rothmans Т. Genius and Biographers: the Fictionalization of Evariste Galois // Amer. Math. Monthly, 1982. Vol. 89, P. 84–106.
В статье приведен подробный перечень источников, на которые опираются биографы Галуа, и обсуждается достоверность различных интерпретаций.
2 Depny P. La vie d'Evariste Galois // Annales Scientifiques de 1'Ecole Normale Superieure, 1986. Vol. 13, P. 197–266.
3 Dumas A. Mes Memoirs. — Editions Gallimard, 1967.
4 Van der Poorten A. Notes on Fermat's Last Theorem. — Wiley, 1996.
Техническое описание доказательства Уайлса, рассчитанное на студентов старших курсов и аспирантов математических специальностей.
ГЛАВА 7
1 Gelbart S. An elementary introduction to the Langlands programme // Bulletin of the American Mathematical Monthly, 1984. Vol. 10, P. 177–219.
Техническое изложение программы Ленглендса, рассчитанное на профессиональных математиков.
2 Wiles A. Modular elliptic curves and Fermat's Last Theorem // Ann. of Math., 1995. Vol. 142, P. 443–551.
Эта статья содержит основную часть предложенного Уайлсом доказательства гипотезы Таниямы-Шимуры и Великой теоремы Ферма.
3 Taylor R., Wiles A. Ring-theoretic properties of certain Hecke algebras // Ann. of Math., 1995. Vol. 142, P. 553–572.
В этой статье приводится описание тех математических методов, которые использовались для восполнения пробелов в варианте доказательства Уайлса 1993 года.
ГЛАВА 8
1 Stewart I. How to succeed in stacking // New Scientist, 13 July 1991, P. 29–32.
2 Morgan J. The death of proof // Scientific American, October 1993, P. 74–82.
3 Appel K., Haken W. The solution of the four-color-map problem // Scientific American, October 1977. P. 108–121.
4 Saaty T. L., Kainen P. C. The Four-Color Problem: Assaults and Conquest. — McGraw-Hill, 1977.
5 Davis O. J., Hersh R. The Mathematical Experience. — Penguin, 1990.
Спасибо, что скачали книгу в бесплатной электронной библиотеке Royallib.ru
Оставить отзыв о книге
Все книги автора
[1]Не могу отказать себе в удовольствии привести сонет А. Шамиссо, написанный по этому поводу:
Во мгле веков пред нашим взором
Блеснула истина. Она,
Как теорема Пифагора,
До наших дней еще верна.
Найдя разгадку, мудрый старец
Был благодарен небесам;
Он сто быков велел зажарить
И в жертву принести богам.
С тех пор быки тревожно дышат, —
Они, кляня дары богов,
О новой истине услышав,
Ужасный поднимают рев.
Их старца имя потрясает,
Их истины лучи слепят;
И, новой жертвы ожидая,
Быки, зажмурившись, дрожат.
— E.G.A.
[2]Задачи занимательные и приятные, связанные с числами. (фр. )
[3]Гарднер М. Математические новеллы. — М.: Мир, 1974; гл. 28 «Краткий трактат о бесполезной красоте совершенных чисел».
[4]Невозможно для куба быть записанным в виде суммы двух кубов, или для четвертой степени быть записанной в виде суммы двух четвертых степеней, или, в общем, для любого числа, которое есть степень больше двух, быть записанной в виде суммы двух таких же степеней. (лат. )
[5]Я нашел поистине удивительное доказательство этого предложения, но поля здесь слишком узки для того, чтобы вместить его. (лат. )
[6]Вспомнилась тут фраза Титчмарша: «Я недавно встретил человека, который сказал мне, что не верит даже в существование минус единицы, так как из этого следует существование квадратного корня из неё».:) — E.G.A.
[7]Приведу иллюстрацию с вселением нового клиента в отель Гильберта. Она позаимствована из книги «Proofs from THE BOOK», выпущенной издательством Springer в 1998 году и переизданной в 2001 году. Авторы: Martin Aigner и Günter M. Ziegler. Мелкая цитата из предисловия авторов к этой книге: "Paul Erdös liked to talk about The Book, in which God maintains the perfect proofs for mathematical theorems, following the dictum of G. H. Hardy that there is no permanent place for ugly mathematics. Erdös also said that you need not believe in God but, as mathematician, you should believe in The Book. We have no definition or characterization of what constitutes a proof from The Book: all we offer here is the examples that we have selected, hoping that our readers will share our enthusiasm about brilliant ideas, clever insights and wonderful observations. We also hope that our readers will enjoy this despite the imperfections of our exposition. The selection is to a great extent influenced by Paul Erdös himself." Вот главу "Множества, функции и гипотеза континуума" эта иллюстрация и открывает. — E.G.A.
[8]Хм… Я где-то читал, что он поплатился жизнью, когда крикнул: «Осторожно! Не наступи на мои чертежи!», но римский солдат, к которому был обращен этот возглас, не обратил внимания, что перед ним безоружный старик. :( А в упомянутой мною раньше книге «Proofs from THE BOOK» главу "Теория чисел" предваряет рисунок, на котором никакого копья нет. Видать, художник тоже не знал подробностей смерти Архимеда. — E.G.A.
[9]Сам бы мог привести пару историй с «ферматистами», которые в своё время услышал от зав. кафедрой алгебры нашего местного университета. Но не веселы они: в сущности, эти «ферматисты» — несчастные люди. И на ICM'98 в Берлине, где Эндрю Уайлс получал Филдсовскую премию, на секции алгебры видел доклады типа "А вот ещё одно доказательство Великой теоремы Ферма". Лучше расскажу про одну из "увёрток от ферматистов", которую где-то вычитал. Учёный секретарь одного из московских академических институтов, не избежавшего нашествия ферматистов, однажды был в отпуске в Молдавии и на рынке купил какую-то снедь, которую ему завернули в местную газету. Вернувшись с рынка, он стал просматривать этот листок и наткнулся на заметку, в которой сообщалось, что местный школьный учитель доказал теорему Ферма, и, как следствие, пелись всякие дифирамбы высокому уровню областной науки. Учёный секретарь вырезал эту заметку, а по возвращении в Москву вставил её в рамку и повесил на стену своего кабинета. Теперь, когда на него «нападал» очередной ферматист, он широким жестом приглашал того ознакомиться с "текущим положением дел". Жизнь явно стала легче. :) — E.G.A.
[10]Это не совсем верно. Развивая идеи Куммера, именно в это или близкое время Д. Гильберт, Э. Нётер, Б. Л. Ван дер Варден и другие, придали алгебре и теории чисел современный облик.
[11]Мы должны знать, мы будем знать (нем. )
[12]Фундаментальные законы арифметики (нем.)
[13]Главный труд (лат .)
[14]Обе теоремы относятся к достаточно богатой математической теории (например, к аксиоматике Пеано теории целых чисел или системе аксиом Цермело–Френкеля). Следует иметь в виду, что здесь приводятся не точные формулировки теорем, а их популярная интерпретация.
[15]А Роджер Фрай (как сказано в "Конкретной математике" Р. Грэхема, Д. Кнута и О. Паташника) затратив 110 часов работы суперкомпьютера Connection Machine, показал, что единственным решением для w < 1 000 000 является 95 8004 + 217 5194 + 414 5604 = 422 4814. — E.G.A.
[16]Название арифметика вычетов, или арифметика остатков, происходит от того, что в ней рассматриваются не сами числа, а остатки от деления на какое-либо число, в данном случае на 5.
[17]Строго говоря программа Ленглендса относится прежде всего к установлению связей между теорией представлений алгебраических групп, теорией модулярных форм и теорией Галуа глобальных полей.
[18]Работы С. Ю. Аракелова не имеют отношения к программе Ленглендса. — Прим. ред
[19]Здесь имеется в виду аналогия между теорией чисел и теорией функций, восходящая к Л. Кронекеру, и особенно развитая в работах Д. Гильберта. — Прим. ред.
[20]Отметим, что Г. Фалтингс не занимался специально теоремой Ферма. О работе Г. Фалтингса и предшествующих исследованиях см. Паршин А. Н., Зархин Ю. Г. Проблемы конечности в диофантовой геометрии. – В кн.: Ленг С. Диофантова геометрия. – М.: Мир, 1986. С. 369–438. — Прим. ред.
[21]Эти утверждения неверны. Для случая алгебраических поверхностей неравенство Мияоки было им же доказано (обобщая предшествующее неравенство Ф. А. Богомолова). То, что арифметический аналог неравенства Мияоки влечет теорему Ферма было показано А. Н. Паршиным. Более подробно см. Паршин А. Н. Дополнение редактора к книге «Алгебра и теория чисел (с приложениями)». – М.: Мир, 1987. С. 267–271. — Прим. ред.
[22]Констанс Рид в своей книге «Гильберт» (М., Наука, 1977) рассказывает об этом так: "Гильберт хотел привести своим слушателям характерные примеры теоретико-числовых проблем, представляющихся на первый взгляд совсем простыми, но решение которых оказывается невероятно трудным. Он упомянул в качестве такого типа проблем гипотезу Римана, теорему Ферма и проблему трансцендентности числа 2√2 (составляющую седьмую из его парижских проблем). Затем он продолжил, сказав, что недавно обнаружился большой прогресс, связанный с гипотезой Римана, и он очень надеется, что сам доживет до ее доказательства. Проблема Ферма стоит уже давно и явно требует совершенно новых методов для своего решения, — быть может, самому молодому слушателю в аудитории удастся дожить до ее решения. Что же касается числа 2√2, то ни один из присутствующих на лекции не доживет до доказательства его трансцендентности!
Две первые из упомянутых Гильбертом проблем не решены до сих пор. Однако десять лет спустя один молодой русский математик по фамилии Гельфонд установил трансцендентность числа 2√(–2). Основываясь на его работе, К.Л. Зигель вскоре доказал требуемую трансцендентность числа 2√2.
Зигель написал Гильберту об этом доказательстве. Он напомнил ему слова, сказанные на лекции в 1920 году, и подчеркнул, что важнейшим моментом здесь была работа Гельфонда. Гильберта часто критиковали за то, что «он ведет себя так, как будто всё сделано в Гёттингене». Теперь он с крайним восторгом ответил на письмо Зигеля, даже не упомянув о достижении молодого русского математика. Он хотел опубликовать только решение Зигеля. Но тот отказался, уверенный, что Гельфонд сам, в конце концов, решит и эту проблему тоже. Гильберт сразу потерял всякий интерес к этому делу". Цитата хоть и великовата, но показывает, что предсказания Гильберта не всегда бывали "исключительно точны". :) — E.G.A.
[23]чересчур завышенная оценка; еще двадцать лет назад было известно, что показатель в теореме Шнирельмана не превышает 20. — E.G.A.
[24]Имеется в виду древнегреческий миф о царе Эдипе. После того, как Эдип разгадал загадку, предложенную ему Сфинксом, Сфинкс бросился в пропасть со скалы.