{
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: '266',
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'
}
}
}