{ localUrl: '../page/mathematical_induction.html', arbitalUrl: 'https://arbital.com/p/mathematical_induction', rawJsonUrl: '../raw/5fz.json', likeableId: '3097', likeableType: 'page', myLikeValue: '0', likeCount: '7', dislikeCount: '0', likeScore: '7', individualLikes: [ 'EricBruylant', 'EliezerYudkowsky', 'KevinClancy', 'EdwinEvans', 'VladArber', 'MalcolmMcCrimmon', 'EricRogstad' ], pageId: 'mathematical_induction', edit: '9', editSummary: '', prevEdit: '8', currentEdit: '9', wasPublished: 'true', type: 'wiki', title: 'Mathematical induction', clickbait: 'Proving a statement about all positive integers by knocking them down like dominoes.', textLength: '3713', alias: 'mathematical_induction', externalUrl: '', sortChildrenBy: 'likes', hasVote: 'false', voteType: '', votesAnonymous: 'false', editCreatorId: 'DylanHendrickson', editCreatedAt: '2016-08-09 12:17:38', pageCreatorId: 'DouglasWeathers', pageCreatedAt: '2016-07-17 15:47:23', seeDomainId: '0', editDomainId: 'AlexeiAndreev', submitToDomainId: '0', isAutosave: 'false', isSnapshot: 'false', isLiveEdit: 'true', isMinorEdit: 'false', indirectTeacher: 'false', todoCount: '0', isEditorComment: 'false', isApprovedComment: 'true', isResolved: 'false', snapshotText: '', anchorContext: '', anchorText: '', anchorOffset: '0', mergedInto: '', isDeleted: 'false', viewCount: '290', text: 'The **principle of mathematical induction** is a proof technique in which a statement, $P(n)$, is proven about a set of [45h natural numbers] $n$. It may be best understood as treating the statements like dominoes: a statement $P(n)$ is true if the $n$-th domino is knocked down. We must knock down a first domino, or prove that a **base case** $P(m)$ is true. Next we must make sure the dominoes are close enough together to fall, or that the **inductive step** holds; in other words, we prove that if $k \\geq m$ and $P(k)$ is true, $P(k+1)$ is true. Then since $P(m)$ is true, $P(m+1)$ is true; and since $P(m+1)$ is true, $P(m+2)$ is true, and so on.\n\nAn example\n=======\n\nWe'll do an example to build our intuition before giving the proper definition of the principle. We'll provide yet another proof that\n$$ 1 + 2 + \\cdots + n = \\frac{n(n+1)}{2}$$\nfor all integers $n \\ge 1$. First, let's check the base case, where $n=1$:\n$$ 1 = \\frac{1(1+1)}{2} = \\frac{2}{2} = 1.$$\nThis is (fairly obviously) true, so we can move forward with the inductive step. The inductive step includes an assumption, namely that the statement is true for some integer $k$ that is larger than the base integer. For our example, if $k\\ge1$, we assume that\n$$1 + 2 + \\cdots + k = \\frac{k(k+1)}{2}$$\nand try to prove that\n$$ 1 + 2 + \\cdots + k + (k+1) = \\frac{(k+1)([k+1]+1)}{2}.$$\nTake our assumption and add $k+1$ to both sides:\n$$1+2+\\cdots + k + (k+1) = \\frac{k(k+1)}{2} + k + 1.$$\nNow the left-hand sides of what we know and what we want are the same. Hopefully the right-hand side will shake out to be the same. Get common denominators so that the right-hand side of the above equation is\n$$\\frac{k(k+1)}{2} + \\frac{2(k+1)}{2} = \\frac{(k+2)(k+1)}{2} = \\frac{(k+1)([k+1]+1)}{2}.$$\nTherefore,\n$$ 1 + 2 + \\cdots + k + (k+1) = \\frac{(k+1)([k+1]+1)}{2}$$\nas desired.\n\nLet $P(n)$ be the statement for $n \\ge 1$ that the sum of all integers between 1 and $n$ is $n(n+1)/2$. At the beginning we showed that the base case, $P(1)$, is true. Next we showed the inductive step, that if $k \\ge 1$ and $P(k)$ is true, then $P(k+1)$ is true. This means that since $P(1)$ is true, $P(2)$ is true; and since $P(2)$ is true, $P(3)$ is true; etc., so that $P(n)$ is true for all integers $n \\ge 1$.\n\nDefinition for the natural numbers\n======\n\nWe are ready to properly define mathematical induction.\n\nWeak mathematical induction\n-------\n\nLet $P(n)$ be a statement about the natural numbers. Then $P$ is true for all $n \\ge m$ if\n\n 1. $P(m)$ is true, and\n 2. For all $k \\ge m$, $P(k+1)$ is true if $P(k)$ is.\n\nStrong mathematical induction\n-----\n\nLet $P(n)$ be a statement about the natural numbers. Then $P$ is true for all $n \\ge m$ if\n\n 1. $P(m)$ is true, and\n 2. For all $k \\ge m$, $P(k)$ is true so long as $P(\\ell)$ is true for all $m \\le \\ell < k$.\n\nA note: **strong mathematical induction** is a variant on mathematical induction by requiring a stronger inductive step, namely that the statement is true for *all* smaller indices, not just the immediate predecessor.\n\nInduction on a well-ordered set\n=====\n\nWell done if your immediate response to the above material was, "Well, am I only restricted to this technique on the natural numbers?" No. As long as your index set is [55r well-ordered], then strong mathematical induction will work.\n\nHowever, if your ordered set is not well-ordered, you can prove properties 1 and 2 above, and still not have it hold for all elements beyond the base case. For instance, consider the set of nonnegative real numbers, and let $P(x)$ be the claim $x\\leq 1$. Then $P(0)$ is true, and for all real numbers $x\\ge 0$, $P(x)$ is true whenever $P(y)$ is true for all $0 \\le y < x$. But of course $P(2)$ is false.', metaText: '', isTextLoaded: 'true', isSubscribedToDiscussion: 'false', isSubscribedToUser: 'false', isSubscribedAsMaintainer: 'false', discussionSubscriberCount: '2', maintainerCount: '2', userSubscriberCount: '0', lastVisit: '', hasDraft: 'false', votes: [], voteSummary: 'null', muVoteSummary: '0', voteScaling: '0', currentUserVote: '-2', voteCount: '0', lockedVoteType: '', maxEditEver: '0', redLinkCount: '0', lockedBy: '', lockedUntil: '', nextPageId: '', prevPageId: '', usedAsMastery: 'false', proposalEditNum: '0', permissions: { edit: { has: 'false', reason: 'You don't have domain permission to edit this page' }, proposeEdit: { has: 'true', reason: '' }, delete: { has: 'false', reason: 'You don't have domain permission to delete this page' }, comment: { has: 'false', reason: 'You can't comment in this domain because you are not a member' }, proposeComment: { has: 'true', reason: '' } }, summaries: {}, creatorIds: [ 'KevinClancy', 'DouglasWeathers', 'PatrickLaVictoir', 'DylanHendrickson' ], childIds: [], parentIds: [ 'proof_technique' ], commentIds: [ '5g9', '5gd' ], questionIds: [], tagIds: [ 'b_class_meta_tag' ], relatedIds: [], markIds: [], explanations: [], learnMore: [], requirements: [], subjects: [], lenses: [], lensParentId: '', pathPages: [], learnMoreTaughtMap: {}, learnMoreCoveredMap: {}, learnMoreRequiredMap: {}, editHistory: {}, domainSubmissions: {}, answers: [], answerCount: '0', commentCount: '0', newCommentCount: '0', linkedMarkCount: '0', changeLogs: [ { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '19024', pageId: 'mathematical_induction', userId: 'EricBruylant', edit: '0', type: 'deleteParent', createdAt: '2016-08-20 13:26:04', auxPageId: 'math', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '19022', pageId: 'mathematical_induction', userId: 'EricBruylant', edit: '0', type: 'newParent', createdAt: '2016-08-20 13:26:02', auxPageId: 'proof_technique', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '18671', pageId: 'mathematical_induction', userId: 'DylanHendrickson', edit: '9', type: 'newEdit', createdAt: '2016-08-09 12:17:38', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '3160', likeableType: 'changeLog', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [], id: '17257', pageId: 'mathematical_induction', userId: 'PatrickLaVictoir', edit: '8', type: 'newEdit', createdAt: '2016-07-21 21:54:28', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17054', pageId: 'mathematical_induction', userId: 'DouglasWeathers', edit: '6', type: 'newEdit', createdAt: '2016-07-17 18:43:52', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17048', pageId: 'mathematical_induction', userId: 'KevinClancy', edit: '0', type: 'newTag', createdAt: '2016-07-17 18:18:21', auxPageId: 'b_class_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '3107', likeableType: 'changeLog', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [], id: '17047', pageId: 'mathematical_induction', userId: 'KevinClancy', edit: '5', type: 'newEdit', createdAt: '2016-07-17 18:07:29', auxPageId: '', oldSettingsValue: '', newSettingsValue: 'Introduced the variable k in the "Definition for the natural numbers" section' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17046', pageId: 'mathematical_induction', userId: 'KevinClancy', edit: '4', type: 'newEdit', createdAt: '2016-07-17 17:38:20', auxPageId: '', oldSettingsValue: '', newSettingsValue: 'Every orderd set, not just well-ordered ones, have a notion of <' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17045', pageId: 'mathematical_induction', userId: 'KevinClancy', edit: '0', type: 'newParent', createdAt: '2016-07-17 17:37:03', auxPageId: 'math', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17043', pageId: 'mathematical_induction', userId: 'KevinClancy', edit: '3', type: 'newEdit', createdAt: '2016-07-17 17:36:34', auxPageId: '', oldSettingsValue: '', newSettingsValue: 'Changed > to geq so that we can induct past he base case.' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17042', pageId: 'mathematical_induction', userId: 'KevinClancy', edit: '2', type: 'newEditProposal', createdAt: '2016-07-17 17:28:47', auxPageId: '', oldSettingsValue: '', newSettingsValue: 'The next sentence does not make sense unless we change > to geq' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17041', pageId: 'mathematical_induction', userId: 'DouglasWeathers', edit: '1', type: 'newEdit', createdAt: '2016-07-17 15:47:23', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' } ], feedSubmissions: [], searchStrings: {}, hasChildren: 'false', hasParents: 'true', redAliases: {}, improvementTagIds: [], nonMetaTagIds: [], todos: [], slowDownMap: 'null', speedUpMap: 'null', arcPageIds: 'null', contentRequests: { fewerWords: { likeableId: '3615', likeableType: 'contentRequest', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [], id: '116', pageId: 'mathematical_induction', requestType: 'fewerWords', createdAt: '2016-10-19 09:15:44' }, lessTechnical: { likeableId: '3278', likeableType: 'contentRequest', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [], id: '12', pageId: 'mathematical_induction', requestType: 'lessTechnical', createdAt: '2016-07-31 07:47:57' }, moreTechnical: { likeableId: '3614', likeableType: 'contentRequest', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [], id: '115', pageId: 'mathematical_induction', requestType: 'moreTechnical', createdAt: '2016-10-19 09:15:40' }, moreWords: { likeableId: '3279', likeableType: 'contentRequest', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [], id: '13', pageId: 'mathematical_induction', requestType: 'moreWords', createdAt: '2016-07-31 07:47:59' }, slowDown: { likeableId: '3100', likeableType: 'contentRequest', myLikeValue: '0', likeCount: '5', dislikeCount: '0', likeScore: '5', individualLikes: [], id: '2', pageId: 'mathematical_induction', requestType: 'slowDown', createdAt: '2016-07-17 18:59:40' }, speedUp: { likeableId: '3099', likeableType: 'contentRequest', myLikeValue: '0', likeCount: '3', dislikeCount: '0', likeScore: '3', individualLikes: [], id: '1', pageId: 'mathematical_induction', requestType: 'speedUp', createdAt: '2016-07-17 18:59:37' } } }