{
  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'
    }
  }
}