#set document(title: "3.5 Induction", author: "OpenStax / XYZ Homework")
#set page(width: 8.5in, height: auto, margin: 1in)
#import "@preview/cetz:0.5.2"
#set text(font: ("STIX Two Text", "Libertinus Serif", "New Computer Modern"), size: 10.5pt, lang: "en")
#show math.equation: set text(font: ("STIX Two Math", "New Computer Modern Math"))
#set par(justify: true, leading: 0.62em, spacing: 0.9em)
#set enum(spacing: 1.1em)   // room between list items so tall inline fractions don't collide
#set list(spacing: 1.1em)
#set table(stroke: 0.5pt + rgb("#c7ccd3"))

#let BLUE = rgb("#183B6F")     // brand navy — section bars + example/solution labels (white on navy 11.09:1)
#let ORANGE = rgb("#A94509")   // brand primary-700 — AA-safe deep orange for TEXT (5.93:1 on white; raw brand #F37021 is 2.94:1 and must never carry text)
#let RED = rgb("#DC2626")      // brand error-600
#let GREEN = rgb("#059669")    // brand success-600 (decoration only; small green text uses green-text #007942)

#show heading.where(level: 1): it => block(width: 100%, above: 0pt, below: 16pt,
  fill: gradient.linear(BLUE, rgb("#2C5AA0")), inset: (x: 14pt, y: 12pt), radius: 3pt,
  text(fill: white, weight: "bold", size: 19pt, it.body))
#show heading.where(level: 2): it => block(width: 100%, above: 18pt, below: 10pt,
  fill: BLUE, inset: (x: 10pt, y: 6pt), radius: 2pt,
  text(fill: white, weight: "bold", size: 12pt, it.body))
#show heading.where(level: 3): it => text(fill: ORANGE, weight: "bold", size: 12.5pt, it.body)
#show heading.where(level: 4): it => text(fill: BLUE, weight: "bold", size: 10.5pt, it.body)

#let examplebox(label, title, body) = block(width: 100%, breakable: true,
  fill: rgb("#EFF1F5"), stroke: 0.5pt + rgb("#CFDDF0"), radius: 4pt, inset: 10pt,
  above: 12pt, below: 12pt)[
  #block(below: 6pt)[#box(fill: BLUE, inset: (x: 6pt, y: 2pt), radius: 2pt,
    text(fill: white, weight: "bold", size: 8.5pt, label)) #h(0.4em) #strong[#title]]
  #body]

// rail = decorative left rule (raw brand token); labelcolor = AA-safe label text shade
#let notebox(label, rail, labelcolor, tint, body) = block(width: 100%, breakable: true, fill: tint,
    stroke: (left: 3pt + rail), inset: (left: 10pt, rest: 8pt), radius: (right: 4pt),
    above: 11pt, below: 11pt)[
    #text(fill: labelcolor, weight: "bold", size: 7.5pt, tracking: 0.5pt)[#upper(label)]
    #linebreak() #body]

#let solutionbox(body) = block(above: 4pt, below: 8pt)[
  #text(fill: BLUE, weight: "bold", size: 8.5pt)[Solution] #linebreak() #body]

#let figph(msg) = block(width: 100%, height: 60pt, fill: rgb("#f6f7f9"),
  stroke: (paint: rgb("#c7ccd3"), dash: "dashed"), radius: 4pt, inset: 10pt)[
  #align(center + horizon, text(fill: rgb("#889"), style: "italic", size: 9pt, msg))]

// Standardize inlined figure sizes: measure the natural CeTZ canvas, then scale to a
// consistent envelope (aspect-aware; see build_typst.py FIG_* constants). Unlike the
// print preamble, dimensions are FLOORED: in an editor a user can trim a figure to a
// degenerate 1-D shape (a bare line), and w/h or tw/w would then divide by zero.
#let _STD_W = 3.5
#let _WIDE_W = 5.6
#let _MAX_H = 3.4
#let _ASPECT_WIDE = 2.2
#let _UPSCALE_MAX = 1.15
#let stdfig(body) = context {
  let m = measure(body)
  let w = calc.max(m.width / 1in, 0.01)
  let h = calc.max(m.height / 1in, 0.01)
  let tw = if w / h > _ASPECT_WIDE { _WIDE_W } else { _STD_W }
  let s = calc.min(tw / w, _MAX_H / h, _UPSCALE_MAX)
  align(center, box(scale(x: s * 100%, y: s * 100%, reflow: true, body)))
}

#show figure: set block(breakable: false)
#set figure(gap: 8pt)
#show figure.caption: set text(size: 8.5pt, fill: rgb("#555"))


    
== 3.5#h(0.6em)Induction


    Mathematical induction is a proof technique,
      not unlike direct proof or proof by contradiction or combinatorial proof.
      You might or might not be familiar with these yet.
      We will consider these in Symbolic Logic and Proofs.
       In other words,
      induction is a style of argument we use to convince ourselves and others that a mathematical statement is always true.
      Many mathematical statements can be proved by simply explaining what they mean.
      Others are very difficult to prove—in fact,
      there are relatively simple mathematical statements which nobody yet knows how to prove.
      To facilitate the discovery of proofs,
      it is important to be familiar with some standard styles of arguments.
      Induction is one such style.
      Let's start with an example:


    
      
=== Stamps


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
You need to mail a package, but don't yet know how much postage you will need.
        You have a large supply of 8-cent stamps and 5-cent stamps.
        Which amounts of postage can you make exactly using these stamps?
        Which amounts are impossible to make?
]


      Perhaps in investigating the problem above you picked some amounts of postage,
      and then figured out whether you could make that amount using just 8-cent and 5-cent stamps.
      Perhaps you did this in order:
      can you make 1 cent of postage?
      Can you make 2 cents? 3 cents?
      And so on.
      If this is what you did,
      you were actually answering a #emph[sequence] of questions.
      We have methods for dealing with sequences.
      Let's see if that helps.


      Actually, we will not make a sequence of questions,
      but rather a sequence of statements.
      Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] 

      be the statement “you can make #math.equation(block: false, alt: "n")[$n$] cents of postage using just 8-cent and 5-cent stamps.”
      Since for each value of #math.equation(block: false, alt: "n")[$n$],
      #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is a statement, it is either true or false.
      So if we form the sequence of statements


      #math.equation(block: true, alt: "P open parenthesis 1 close parenthesis , P open parenthesis 2 close parenthesis , P open parenthesis 3 close parenthesis , P open parenthesis 4 close parenthesis , and so on")[$P ( 1 ) , P ( 2 ) , P ( 3 ) , P ( 4 ) , …$]
      ,
      the sequence will consist of #math.equation(block: false, alt: "T")[$T$]'s
      (for true)
      and #math.equation(block: false, alt: "F")[$F$]'s
      (for false).
      In our particular case the sequence starts


      #math.equation(block: true, alt: "F , F , F , F , T , F , F , T , F , T , F , F , T , and so on")[$F , F , F , F , T , F , F , T , F , T , F , F , T , …$]
      because #math.equation(block: false, alt: "P open parenthesis 1 close parenthesis , P open parenthesis 2 close parenthesis , P open parenthesis 3 close parenthesis , P open parenthesis 4 close parenthesis")[$P ( 1 ) , P ( 2 ) , P ( 3 ) , P ( 4 )$] are all false
      (you cannot make 1, 2, 3, or 4 cents of postage)
      but #math.equation(block: false, alt: "P open parenthesis 5 close parenthesis")[$P ( 5 )$] is true
      (use one 5-cent stamp),
      and so on.


      Let's think a bit about how we could find the value of #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] for some specific #math.equation(block: false, alt: "n")[$n$]
      (the “value” will be either #math.equation(block: false, alt: "T")[$T$] or #math.equation(block: false, alt: "F")[$F$]).
      How did we find the value of the #math.equation(block: false, alt: "n")[$n$]th term of a sequence of numbers?
      How did we find #math.equation(block: false, alt: "a sub n")[$a_(n)$]?
      There were two ways we could do this:
      either there was a closed formula for #math.equation(block: false, alt: "a sub n")[$a_(n)$],
      so we could plug in #math.equation(block: false, alt: "n")[$n$] into the formula and get our output value,
      or we had a recursive definition for the sequence,
      so we could use the previous terms of the sequence to compute the #math.equation(block: false, alt: "n")[$n$]th term.
      When dealing with sequences of statements,
      we could use either of these techniques as well.
      Maybe there is a way to use #math.equation(block: false, alt: "n")[$n$] itself to determine whether we can make #math.equation(block: false, alt: "n")[$n$] cents of postage.
      That would be something like a closed formula.
      Or instead we could use the previous terms in the sequence
      (of statements)
      to determine whether we can make #math.equation(block: false, alt: "n")[$n$] cents of postage.
      That is, if we know the value of #math.equation(block: false, alt: "P open parenthesis n minus 1 close parenthesis")[$P ( n − 1 )$], can we get from that to
      the value of #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$]?
      That would be something like a recursive definition for the sequence.
      Remember, finding recursive definitions for sequences was often easier than finding closed formulas.
      The same is true here.


      Suppose I told you that #math.equation(block: false, alt: "P open parenthesis 43 close parenthesis")[$P ( 43 )$] was true
      (it is).
      Can you determine from this fact the value of #math.equation(block: false, alt: "P open parenthesis 44 close parenthesis")[$P ( 44 )$] (whether it true or false)?
      Yes you can.
      Even if we don't know how exactly we made 43 cents out of the 5-cent and 8-cent stamps,
      we do know that there was some way to do it.
      What if that way used at least three 5-cent stamps (making 15 cents)?
      We could replace those three 5-cent stamps with two 8-cent stamps
      (making 16 cents).
      The total postage has gone up by 1, so we have a way to make 44 cents,
      so #math.equation(block: false, alt: "P open parenthesis 44 close parenthesis")[$P ( 44 )$] is true.
      Of course, we assumed that we had at least three 5-cent stamps.
      What if we didn't?
      Then we must have at least three 8-cent stamps
      (making 24 cents).
      If we replace those three 8-cent stamps with five 5-cent stamps (making 25 cents) then again we have bumped up our total by 1 cent so we can make 44 cents,
      so #math.equation(block: false, alt: "P open parenthesis 44 close parenthesis")[$P ( 44 )$] is true.


      Notice that we have not said how to make 44 cents,
      just that we can, on the basis that we can make 43 cents.
      How do we know we can make 43 cents?
      Perhaps because we know we can make #math.equation(block: false, alt: "42")[$42$] 

      cents, which we know we can do because we know we can make 41 cents,
      and so on.
      It's a recursion!
      As with a recursive definition of a numerical sequence,
      we must specify our initial value.
      In this case, the initial value is
      “#math.equation(block: false, alt: "P open parenthesis 1 close parenthesis")[$P ( 1 )$] is false.” That's not good,
      since our recurrence relation just says that #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true #emph[if]
      #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is also true.
      We need to start the process with a true #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$].
      So instead, we might want to use
      “#math.equation(block: false, alt: "P open parenthesis 28 close parenthesis")[$P ( 28 )$] is true”
      as the initial condition.


      Putting this all together we arrive at the following fact:
      it is possible to (exactly) make any amount of postage greater than 27 cents using just 5-cent and 8-cent stamps.
      This is not claiming that there are no amounts less than 27 cents which can also be made.
       In other words, #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true for any #math.equation(block: false, alt: "k greater than or equal to 28")[$k ≥ 28$].
      To prove this, we could do the following:


      + Demonstrate that #math.equation(block: false, alt: "P open parenthesis 28 close parenthesis")[$P ( 28 )$] is true.
+ Prove that if #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true,
            then #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true
            (for any #math.equation(block: false, alt: "k greater than or equal to 28")[$k ≥ 28$]).


      Suppose we have done this.
      Then we know that the 28th term of the sequence above is a #math.equation(block: false, alt: "T")[$T$]
      (using step 1, the initial condition or #strong[base case]),
      
      
      and that every term after the 28th is #math.equation(block: false, alt: "T")[$T$] also
      (using step 2, the recursive part or
      #strong[inductive case]).
      
      
      Here is what the proof would actually look like.


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement
        “it is possible to make exactly #math.equation(block: false, alt: "n")[$n$] cents of postage using 5-cent and 8-cent stamps.”
        We will show #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 28")[$n ≥ 28$].


        First, we show that #math.equation(block: false, alt: "P open parenthesis 28 close parenthesis")[$P ( 28 )$] is true:
        #math.equation(block: false, alt: "28 equals 4 times 5 plus 1 times 8")[$28 = 4 ⋅ 5 + 1 ⋅ 8$],
        so we can make #math.equation(block: false, alt: "28")[$28$] cents using four 5-cent stamps and one 8-cent stamp.


        Now suppose #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true for some arbitrary #math.equation(block: false, alt: "k greater than or equal to 28")[$k ≥ 28$].
        Then it is possible to make #math.equation(block: false, alt: "k")[$k$] cents using 5-cent and 8-cent stamps.
        Note that since #math.equation(block: false, alt: "k greater than or equal to 28")[$k ≥ 28$],
        it cannot be that we use fewer than three 5-cent stamps #emph[and]
        fewer than three 8-cent stamps:
        using two of each would give only 26 cents.
        Now if we have made #math.equation(block: false, alt: "k")[$k$] cents using at least three 5-cent stamps,
        replace three 5-cent stamps by two 8-cent stamps.
        This replaces 15 cents of postage with 16 cents,
        moving from a total of #math.equation(block: false, alt: "k")[$k$] cents to #math.equation(block: false, alt: "k plus 1")[$k + 1$] cents.
        Thus #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true.
        On the other hand,
        if we have made #math.equation(block: false, alt: "k")[$k$] cents using at least three 8-cent stamps,
        then we can replace three 8-cent stamps with five 5-cent stamps,
        moving from 24 cents to 25 cents,
        giving a total of #math.equation(block: false, alt: "k plus 1")[$k + 1$] cents of postage.
        So in this case as well #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true.


        Therefore, by the principle of mathematical induction,
        #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 28")[$n ≥ 28$].
]


    
    
      
=== Formalizing Proofs


      What we did in the stamp example above works for many types of problems.
      Proof by induction is useful when trying to prove statements about all natural numbers,
      or all natural numbers greater than some fixed first case (like 28 in the example above),
      and in some other situations too.
      In particular,
      induction should be used when there is some way to go from one case to the next – when you can see how to always “do one more.”


      This is a big idea.
      Thinking about a problem #emph[inductively]
      can give new insight into the problem.
      For example, to really understand the stamp problem,
      you should think about how any amount of postage
      (greater than 28 cents)
      can be made
      (this is non-inductive reasoning)
      and also how the ways in which postage can be made
      #emph[changes] as the amount increases
      (inductive reasoning).
      When you are asked to provide a proof by induction,
      you are being asked to think about the problem #emph[dynamically];
      how does increasing #math.equation(block: false, alt: "n")[$n$] change the problem?


      But there is another side to proofs by induction as well.
      In mathematics, it is not enough to understand a problem,
      you must also be able to communicate the problem to others.
      Like any discipline, mathematics has standard language and style,
      allowing mathematicians to share their ideas efficiently.
      Proofs by induction have a certain formal style,
      and being able to write in this style is important.
      It allows us to keep our ideas organized and might even help us with formulating a proof.


      Here is the general structure of a proof by mathematical induction:


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
#emph[Induction Proof Structure]


        Start by saying what the statement is that you want to prove: “Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement…” To prove that #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 0")[$n ≥ 0$], you must prove two facts:


        + Base case: Prove that #math.equation(block: false, alt: "P open parenthesis 0 close parenthesis")[$P ( 0 )$] is true.
              You do this directly.
              This is often easy.
+ Inductive case: Prove that
              #math.equation(block: false, alt: "P open parenthesis k close parenthesis → P open parenthesis k plus 1 close parenthesis")[$P ( k ) → P ( k + 1 )$] for all #math.equation(block: false, alt: "k greater than or equal to 0")[$k ≥ 0$].
              That is, prove that for any #math.equation(block: false, alt: "k greater than or equal to 0")[$k ≥ 0$] if #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true,
              then #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true as well.
              This is the proof of an if
              … then
              … statement,
              so you can assume #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true (#math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is called the
              #emph[inductive hypothesis]).
                
            You must then explain why #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is also true, given that assumption.


        Assuming you are successful on both parts above,
        you can conclude,
        “Therefore by the principle of mathematical induction,
        the statement #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 0")[$n ≥ 0$].”
]


      Sometimes the statement #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] will only be true for values of #math.equation(block: false, alt: "n greater than or equal to 4")[$n ≥ 4$],
      for example, or some other value.
      In such cases, replace all the 0's above with 4's
      (or the other value).


      The other advantage of formalizing inductive proofs is it allows us to verify that the logic behind this style of argument is valid.
      Why does induction work?
      Think of a row of dominoes set up standing on their edges.
      We want to argue that in a minute,
      all the dominoes will have fallen down.
      For this to happen, you will need to push the first domino.
      That is the base case.
      It will also have to be that the dominoes are close enough together that when any particular domino falls,
      it will cause the next domino to fall.
      That is the inductive case.
      If both of these conditions are met,
      you push the first domino over and each domino will cause the next to fall,
      then all the dominoes will fall.


      Induction is powerful!
      Think how much easier it is to knock over dominoes when you don't have to push over each domino yourself.
      You just start the chain reaction,
      and the rely on the relative nearness of the dominoes to take care of the rest.


      Think about our study of sequences.
      It is easier to find recursive definitions for sequences than closed formulas.
      Going from one case to the next is easier than going directly to a particular case.
      That is what is so great about induction.
      Instead of going directly to the (arbitrary) case for #math.equation(block: false, alt: "n")[$n$],
      we just need to say how to get from one case to the next.


      When you are asked to prove a statement by mathematical induction,
      you should first think about #emph[why] the statement is true,
      using inductive reasoning.
      Explain why induction is the right thing to do,
      and roughly why the inductive case will work.
      Then, sit down and write out a careful,
      formal proof using the structure above.


    
    
      
=== Examples


      Here are some examples of proof by mathematical induction.


      #examplebox("Example 1")[][
Prove for each natural number #math.equation(block: false, alt: "n greater than or equal to 1")[$n ≥ 1$] that #math.equation(block: false, alt: "1 plus 2 plus 3 plus ⋯ plus n equals the fraction n open parenthesis n plus 1 close parenthesis over 2")[$1 + 2 + 3 + ⋯ + n = frac(n ( n + 1 ), 2)$].


        
        #solutionbox[
First, let's think inductively about this equation.
          In fact, we know this is true for other reasons
          (reverse and add comes to mind).
          But why might induction be applicable?
          The left-hand side adds up the numbers from 1 to #math.equation(block: false, alt: "n")[$n$].
          If we know how to do that,
          adding just one more term (#math.equation(block: false, alt: "n plus 1")[$n + 1$]) would not be that hard.
          For example, if #math.equation(block: false, alt: "n equals 100")[$n = 100$],
          suppose we know that the sum of the first 100 numbers is #math.equation(block: false, alt: "5050")[$5050$]
          (so #math.equation(block: false, alt: "1 plus 2 plus 3 plus ⋯ plus 100 equals 5050")[$1 + 2 + 3 + ⋯ + 100 = 5050$], which is true).
          Now to find the sum of the first 101 numbers,
          it makes more sense to just add 101 to 5050,
          instead of computing the entire sum again.
          We would have #math.equation(block: false, alt: "1 plus 2 plus 3 plus ⋯ plus 100 plus 101 equals 5050 plus 101 equals 5151")[$1 + 2 + 3 + ⋯ + 100 + 101 = 5050 + 101 = 5151$].
          In fact, it would always be easy to add just one more term.
          This is why we should use induction.


          Now the formal proof:


          #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement #math.equation(block: false, alt: "1 plus 2 plus 3 plus ⋯ plus n equals the fraction n open parenthesis n plus 1 close parenthesis over 2")[$1 + 2 + 3 + ⋯ + n = frac(n ( n + 1 ), 2)$].
            We will show that #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all natural numbers #math.equation(block: false, alt: "n greater than or equal to 1")[$n ≥ 1$].


            Base case: #math.equation(block: false, alt: "P open parenthesis 1 close parenthesis")[$P ( 1 )$] is the statement
            #math.equation(block: false, alt: "1 equals the fraction 1 open parenthesis 1 plus 1 close parenthesis over 2")[$1 = frac(1 ( 1 + 1 ), 2)$] which is clearly true.


            Inductive case: Let #math.equation(block: false, alt: "k greater than or equal to 1")[$k ≥ 1$] be a natural number.
            Assume (for induction) that #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true.
            That means #math.equation(block: false, alt: "1 plus 2 plus 3 plus ⋯ plus k equals the fraction k open parenthesis k plus 1 close parenthesis over 2")[$1 + 2 + 3 + ⋯ + k = frac(k ( k + 1 ), 2)$].
            We will prove that #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true as well.
            That is, we must prove that #math.equation(block: false, alt: "1 plus 2 plus 3 plus ⋯ plus k plus open parenthesis k plus 1 close parenthesis equals the fraction open parenthesis k plus 1 close parenthesis open parenthesis k plus 2 close parenthesis over 2")[$1 + 2 + 3 + ⋯ + k + ( k + 1 ) = frac(( k + 1 ) ( k + 2 ), 2)$].
            To prove this equation,
            start by adding #math.equation(block: false, alt: "k plus 1")[$k + 1$] to both sides of the inductive hypothesis:


            #math.equation(block: true, alt: "1 plus 2 plus 3 plus ⋯ plus k plus open parenthesis k plus 1 close parenthesis equals the fraction k open parenthesis k plus 1 close parenthesis over 2 plus open parenthesis k plus 1 close parenthesis")[$1 + 2 + 3 + ⋯ + k + ( k + 1 ) = frac(k ( k + 1 ), 2) + ( k + 1 )$]
            .


            Now, simplifying the right side we get:


            #math.equation(block: true, alt: "the fraction k open parenthesis k plus 1 close parenthesis over 2 plus k plus 1, equals the fraction k open parenthesis k plus 1 close parenthesis over 2 plus the fraction 2 open parenthesis k plus 1 close parenthesis over 2; equals the fraction k open parenthesis k plus 1 close parenthesis plus 2 open parenthesis k plus 1 close parenthesis over 2; equals the fraction open parenthesis k plus 2 close parenthesis open parenthesis k plus 1 close parenthesis over 2")[$frac(k ( k + 1 ), 2) + k + 1 & = frac(k ( k + 1 ), 2) + frac(2 ( k + 1 ), 2) \  & = frac(k ( k + 1 ) + 2 ( k + 1 ), 2) \  & = frac(( k + 2 ) ( k + 1 ), 2)$]
            .


            Thus #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true,
            so by the principle of mathematical induction #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all natural numbers #math.equation(block: false, alt: "n greater than or equal to 1")[$n ≥ 1$].
]
]
]


      Note that in the part of the proof in which we proved #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] from #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$],
      we used the equation #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$].
      This was the inductive hypothesis.
      
      Seeing how to use the inductive hypotheses is usually straight forward when proving a fact about a sum like this.
      In other proofs, it can be less obvious where it fits in.


      #examplebox("Example 2")[][
Prove that for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$],
          #math.equation(block: false, alt: "6 to the power n minus 1")[$6^(n) − 1$] is a multiple of 5.


        
        #solutionbox[
Again, start by understanding the dynamics of the problem.
          What does increasing #math.equation(block: false, alt: "n")[$n$] do?
          Let's try with a few examples.
          If #math.equation(block: false, alt: "n equals 1")[$n = 1$], then yes, #math.equation(block: false, alt: "6 to the power 1 minus 1 equals 5")[$6^(1) − 1 = 5$] is a multiple of 5.
          What does incrementing #math.equation(block: false, alt: "n")[$n$] to 2 look like?
          We get #math.equation(block: false, alt: "6 squared minus 1 equals 35")[$6^(2) − 1 = 35$], which again is a multiple of 5.
          Next, #math.equation(block: false, alt: "n equals 3")[$n = 3$]: but instead of just finding #math.equation(block: false, alt: "6 cubed minus 1")[$6^(3) − 1$],
          what did the increase in #math.equation(block: false, alt: "n")[$n$] do?
          We will still subtract 1, but now we are multiplying by another 6 first.
          Viewed another way,
          we are multiplying a number which is one more than a multiple of 5 by 6
          (because #math.equation(block: false, alt: "6 squared minus 1")[$6^(2) − 1$] is a multiple of 5, so #math.equation(block: false, alt: "6 squared")[$6^(2)$] is one more than a multiple of 5).
          What do numbers which are one more than a multiple of 5 look like?
          They must have last digit 1 or 6.
          What happens when you multiply such a number by 6?
          Depends on the number, but in any case,
          the last digit of the new number must be a 6.
          And then if you subtract 1, you get last digit 5, so a multiple of 5.


          The point is, every time we multiply by just one more six,
          we still get a number with last digit 6, so subtracting 1 gives us a multiple of 5.
          Now the formal proof:


          #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement,
            “#math.equation(block: false, alt: "6 to the power n minus 1")[$6^(n) − 1$] is a multiple of 5.”
            We will prove that #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].


            Base case: #math.equation(block: false, alt: "P open parenthesis 0 close parenthesis")[$P ( 0 )$] is true:
            #math.equation(block: false, alt: "6 to the power 0 minus 1 equals 0")[$6^(0) − 1 = 0$] which is a multiple of 5.


            Inductive case: Let #math.equation(block: false, alt: "k")[$k$] be an arbitrary natural number.
            Assume, for induction, that #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true.
            That is, #math.equation(block: false, alt: "6 to the power k minus 1")[$6^(k) − 1$] is a multiple of #math.equation(block: false, alt: "5")[$5$].
            Then #math.equation(block: false, alt: "6 to the power k minus 1 equals 5 j")[$6^(k) − 1 = 5 j$] for some integer #math.equation(block: false, alt: "j")[$j$].
            This means that #math.equation(block: false, alt: "6 to the power k equals 5 j plus 1")[$6^(k) = 5 j + 1$].
            Multiply both sides by #math.equation(block: false, alt: "6")[$6$]:


            #math.equation(block: true, alt: "6 to the power k plus 1 equals 6 open parenthesis 5 j plus 1 close parenthesis equals 30 j plus 6")[$6^(k + 1) = 6 ( 5 j + 1 ) = 30 j + 6$]
            .


            But we want to know about #math.equation(block: false, alt: "6 to the power k plus 1 minus 1")[$6^(k + 1) − 1$],
            so subtract 1 from both sides:


            #math.equation(block: true, alt: "6 to the power k plus 1 minus 1 equals 30 j plus 5")[$6^(k + 1) − 1 = 30 j + 5$]
            .


            Of course #math.equation(block: false, alt: "30 j plus 5 equals 5 open parenthesis 6 j plus 1 close parenthesis")[$30 j + 5 = 5 ( 6 j + 1 )$], so is a multiple of 5.


            Therefore #math.equation(block: false, alt: "6 to the power k plus 1 minus 1")[$6^(k + 1) − 1$] is a multiple of 5, or in other words,
            #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true.
            Thus, by the principle of mathematical induction #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
]
]
]


      We had to be a little bit clever (i.e., use some algebra) to locate the #math.equation(block: false, alt: "6 to the power k minus 1")[$6^(k) − 1$] inside of
      #math.equation(block: false, alt: "6 to the power k plus 1 minus 1")[$6^(k + 1) − 1$] before we could apply the inductive hypothesis.
      This is what can make inductive proofs challenging.


      In the two examples above, we started with #math.equation(block: false, alt: "n equals 1")[$n = 1$] or #math.equation(block: false, alt: "n equals 0")[$n = 0$].
      We can start later if we need to.


      #examplebox("Example 3")[][
Prove that #math.equation(block: false, alt: "n squared less than 2 to the power n")[$n^(2) < 2^(n)$] for all integers #math.equation(block: false, alt: "n greater than or equal to 5")[$n ≥ 5$].


        
        #solutionbox[
First, the idea of the argument.
          What happens when we increase #math.equation(block: false, alt: "n")[$n$] by 1?
          On the left-hand side,
          we increase the base of the square and go to the next square number.
          On the right-hand side, we increase the power of 2.
          This means we double the number.
          So the question is,
          how does doubling a number relate to increasing to the next square?
          Think about what the difference of two consecutive squares looks like.
          We have #math.equation(block: false, alt: "open parenthesis n plus 1 close parenthesis squared minus n squared")[$( n + 1 )^(2) − n^(2)$].
          This factors:


          #math.equation(block: true, alt: "open parenthesis n plus 1 close parenthesis squared minus n squared equals open parenthesis n plus 1 minus n close parenthesis open parenthesis n plus 1 plus n close parenthesis equals 2 n plus 1")[$( n + 1 )^(2) − n^(2) = ( n + 1 − n ) ( n + 1 + n ) = 2 n + 1$]
          .


          But doubling the right-hand side increases it by #math.equation(block: false, alt: "2 to the power n")[$2^(n)$],
          since #math.equation(block: false, alt: "2 to the power n plus 1 equals 2 to the power n plus 2 to the power n")[$2^(n + 1) = 2^(n) + 2^(n)$].
          When #math.equation(block: false, alt: "n")[$n$] is large enough, #math.equation(block: false, alt: "2 to the power n greater than 2 n plus 1")[$2^(n) > 2 n + 1$].


          What we are saying here is that each time #math.equation(block: false, alt: "n")[$n$] increases,
          the left-hand side grows by less than the right-hand side.
          So if the left-hand side starts smaller
          (as it does when #math.equation(block: false, alt: "n equals 5")[$n = 5$]),
          it will never catch up.
          Now the formal proof:


          #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement #math.equation(block: false, alt: "n squared less than 2 to the power n")[$n^(2) < 2^(n)$].
            We will prove #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all integers #math.equation(block: false, alt: "n greater than or equal to 5")[$n ≥ 5$].


            Base case: #math.equation(block: false, alt: "P open parenthesis 5 close parenthesis")[$P ( 5 )$] is the statement #math.equation(block: false, alt: "5 squared less than 2 to the power 5")[$5^(2) < 2^(5)$].
            Since #math.equation(block: false, alt: "5 squared equals 25")[$5^(2) = 25$] and #math.equation(block: false, alt: "2 to the power 5 equals 32")[$2^(5) = 32$],
            we see that #math.equation(block: false, alt: "P open parenthesis 5 close parenthesis")[$P ( 5 )$] is indeed true.


            Inductive case: Let #math.equation(block: false, alt: "k greater than or equal to 5")[$k ≥ 5$] be an arbitrary integer.
            Assume, for induction, that #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true.
            That is, assume #math.equation(block: false, alt: "k squared less than 2 to the power k")[$k^(2) < 2^(k)$].
            We will prove that #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true,
            i.e., #math.equation(block: false, alt: "open parenthesis k plus 1 close parenthesis squared less than 2 to the power k plus 1")[$( k + 1 )^(2) < 2^(k + 1)$].
            To prove such an inequality,
            start with the left-hand side and work towards the right-hand side:


            #math.equation(block: true, alt: "open parenthesis k plus 1 close parenthesis squared, equals k squared plus 2 k plus 1; less than 2 to the power k plus 2 k plus 1, and so on by the inductive hypothesis.; less than 2 to the power k plus 2 to the power k, and so on since 2 k plus 1 less than 2 to the power k for k greater than or equal to 5.; equals 2 to the power k plus 1.")[$( k + 1 )^(2) & = k^(2) + 2 k + 1 &  \  & < 2^(k) + 2 k + 1 & … "by the inductive hypothesis." \  & < 2^(k) + 2^(k) & … " since " 2 k + 1 < 2^(k) " for " k ≥ 5. \  & = 2^(k + 1) . &$]
            Following the equalities and inequalities through,
            we get #math.equation(block: false, alt: "open parenthesis k plus 1 close parenthesis squared less than 2 to the power k plus 1")[$( k + 1 )^(2) < 2^(k + 1)$],
            in other words, #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$].
            Therefore by the principle of mathematical induction,
            #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 5")[$n ≥ 5$].
]
]
]


      The previous example might remind you of the
      #emph[racetrack principle] from calculus,
      
      which says that if #math.equation(block: false, alt: "f open parenthesis a close parenthesis less than g open parenthesis a close parenthesis")[$f ( a ) < g ( a )$],
      and #math.equation(block: false, alt: "f prime open parenthesis x close parenthesis less than g prime open parenthesis x close parenthesis")[$f^(′) ( x ) < g^(′) ( x )$] for
      #math.equation(block: false, alt: "x greater than a")[$x > a$], then #math.equation(block: false, alt: "f open parenthesis x close parenthesis less than g open parenthesis x close parenthesis")[$f ( x ) < g ( x )$] for #math.equation(block: false, alt: "x greater than a")[$x > a$].
      Same idea: the larger function is increasing at a faster rate than the smaller function,
      so the larger function will stay larger.
      In discrete math, we don't have derivatives,
      so we look at differences.
      Thus induction is the way to go.


      
        
==== Warning:


        With great power, comes great responsibility.
        Induction isn't magic.
        It seems very powerful to be able to assume #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true.
        After all, we are trying to prove #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true and the only difference is in the variable:
        #math.equation(block: false, alt: "k")[$k$] vs. #math.equation(block: false, alt: "n")[$n$].
        Are we assuming that what we want to prove is true?
        Not really.
        We assume #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true only for the sake of proving that #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true.


        Still you might start to believe that you can prove anything with induction.
        Consider this incorrect “proof” that every Canadian
            
        has the same eye color: Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement that any #math.equation(block: false, alt: "n")[$n$] Canadians have the same eye color. #math.equation(block: false, alt: "P open parenthesis 1 close parenthesis")[$P ( 1 )$] is true,
        since everyone has the same eye color as themselves.
        Now assume #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true.
        That is, assume that in any group of #math.equation(block: false, alt: "k")[$k$] Canadians,
        everyone has the same eye color.
        Now consider an arbitrary group of #math.equation(block: false, alt: "k plus 1")[$k + 1$] Canadians.
        The first #math.equation(block: false, alt: "k")[$k$] of these must all have the same eye color,
        since #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true.
        Also, the last #math.equation(block: false, alt: "k")[$k$] of these must have the same eye color,
        since #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true.
        So in fact, everyone the group must have the same eye color.
        Thus #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true.
        So by the principle of mathematical induction,
        #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n")[$n$].


        Clearly something went wrong.
        The problem is that the proof that #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] implies #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] assumes that #math.equation(block: false, alt: "k greater than or equal to 2")[$k ≥ 2$].
        We have only shown #math.equation(block: false, alt: "P open parenthesis 1 close parenthesis")[$P ( 1 )$] is true.
        In fact, #math.equation(block: false, alt: "P open parenthesis 2 close parenthesis")[$P ( 2 )$] is false.


      
    
    
      
=== Strong Induction


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Start with a square piece of paper.
        You want to cut this square into smaller squares, leaving no waste
        (every piece of paper you end up with must be a square).
        Obviously it is possible to cut the square into 4 squares.
        You can also cut it into 9 squares.
        It turns out you can cut the square into 7 squares
        (although not all the same size).
        What other numbers of squares could you end up with?
]


      Sometimes, to prove that #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true,
      it would be helpful to know that #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] #emph[and] #math.equation(block: false, alt: "P open parenthesis k minus 1 close parenthesis")[$P ( k − 1 )$] #emph[and]
      #math.equation(block: false, alt: "P open parenthesis k minus 2 close parenthesis")[$P ( k − 2 )$] are all true.
      Consider the following puzzle:


      You have a rectangular chocolate bar,
        made up of #math.equation(block: false, alt: "n")[$n$] identical squares of chocolate.
        You can take such a bar and break it along any row or column.
        How many times will you have to break the bar to reduce it to #math.equation(block: false, alt: "n")[$n$] single chocolate squares?


      At first, this question might seem impossible.
      Perhaps I meant to ask for the #emph[smallest] number of breaks needed?
      Let's investigate.


      Start with some small cases.
      If #math.equation(block: false, alt: "n equals 2")[$n = 2$], you must have a #math.equation(block: false, alt: "1 times 2")[$1 × 2$] rectangle,
      which can be reduced to single pieces in one break.
      With #math.equation(block: false, alt: "n equals 3")[$n = 3$], we must have a #math.equation(block: false, alt: "1 times 3")[$1 × 3$] bar,
      which requires two breaks:
      the first break creates a single square and a #math.equation(block: false, alt: "1 times 2")[$1 × 2$] bar,
      which we know takes one (more) break.


      What about #math.equation(block: false, alt: "n equals 4")[$n = 4$]?
      Now we could have a #math.equation(block: false, alt: "2 times 2")[$2 × 2$] bar,
      or a #math.equation(block: false, alt: "1 times 4")[$1 × 4$] bar.
      In the first case, break the bar into two #math.equation(block: false, alt: "2 times 2")[$2 × 2$] bars,
      each which require one more break
      (that's a total of three breaks required).
      If we started with a #math.equation(block: false, alt: "1 times 4")[$1 × 4$] bar,
      we have choices for our first break.
      We could break the bar in half,
      creating two #math.equation(block: false, alt: "1 times 2")[$1 × 2$] bars,
      or we could break off a single square,
      leaving a #math.equation(block: false, alt: "1 times 3")[$1 × 3$] bar.
      But either way,
      we still need two more breaks, giving a total of three.


      It is starting to look like no matter how we break the bar
      (and no matter how the #math.equation(block: false, alt: "n")[$n$] squares are arranged into a rectangle),
      we will always have the same number of breaks required.
      It also looks like that number is one less than #math.equation(block: false, alt: "n")[$n$]:


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Given a #math.equation(block: false, alt: "n")[$n$]-square rectangular chocolate bar,
          it always takes #math.equation(block: false, alt: "n minus 1")[$n − 1$] breaks to reduce the bar to single squares.
]


      It makes sense to prove this by induction because after breaking the bar once,
      you are left with #emph[smaller] chocolate bars.
      Reducing to smaller cases is what induction is all about.
      We can inductively assume we already know how to deal with these smaller bars.
      The problem is,
      if we are trying to prove the inductive case about a #math.equation(block: false, alt: "open parenthesis k plus 1 close parenthesis")[$( k + 1 )$]-square bar,
      we don't know that after the first break the remaining bar will have #math.equation(block: false, alt: "k")[$k$] squares.
      So we really need to assume that our conjecture is true for all cases less than #math.equation(block: false, alt: "k plus 1")[$k + 1$].


      Is it valid to make this stronger assumption?
      Remember, in induction we are attempting to prove that #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n")[$n$].
      What if that were not the case?
      Then there would be some first #math.equation(block: false, alt: "n sub 0")[$n_(0)$] for which #math.equation(block: false, alt: "P open parenthesis n sub 0 close parenthesis")[$P ( n_(0) )$] was false.
      Since #math.equation(block: false, alt: "n sub 0")[$n_(0)$] is the #emph[first] counterexample,
      we know that #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n less than n sub 0")[$n < n_(0)$].
      Now we proceed to prove that #math.equation(block: false, alt: "P open parenthesis n sub 0 close parenthesis")[$P ( n_(0) )$] is actually true,
      based on the assumption that #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all smaller #math.equation(block: false, alt: "n")[$n$].


      This is quite an advantage: we now have a stronger inductive hypothesis.
      
      We can assume that #math.equation(block: false, alt: "P open parenthesis 1 close parenthesis")[$P ( 1 )$], #math.equation(block: false, alt: "P open parenthesis 2 close parenthesis")[$P ( 2 )$], #math.equation(block: false, alt: "P open parenthesis 3 close parenthesis")[$P ( 3 )$],
      … #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true,
      just to show that #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true.
      Previously, we just assumed #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] for this purpose.


      It is slightly easier if we change our variables for strong induction.
      Here is what the formal proof would look like:


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
#emph[Strong Induction Proof Structure]


        Again, start by saying what you want to prove:
        “Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement…”
        Then establish two facts:


        + Base case: Prove that #math.equation(block: false, alt: "P open parenthesis 0 close parenthesis")[$P ( 0 )$] is true.
+ Inductive case: Assume #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true for all #math.equation(block: false, alt: "k less than n")[$k < n$].
              Prove that #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true.


        Conclude, “therefore, by strong induction,
        #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than 0")[$n > 0$].”
]


      Of course, it is acceptable to replace 0 with a larger base case if needed.
      Technically,
      strong induction does not require you to prove a separate base case.
      This is because when proving the inductive case,
      you must show that #math.equation(block: false, alt: "P open parenthesis 0 close parenthesis")[$P ( 0 )$] is true,
      assuming #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true for all #math.equation(block: false, alt: "k less than 0")[$k < 0$].
      But this is not any help so you end up proving #math.equation(block: false, alt: "P open parenthesis 0 close parenthesis")[$P ( 0 )$] anyway.
      To be on the safe side, we will always include the base case separately.


      Let's prove our conjecture about the chocolate bar puzzle:


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement,
        “it takes #math.equation(block: false, alt: "n minus 1")[$n − 1$] breaks to reduce a #math.equation(block: false, alt: "n")[$n$]-square chocolate bar to single squares.”


        Base case: Consider #math.equation(block: false, alt: "P open parenthesis 2 close parenthesis")[$P ( 2 )$].
        The squares must be arranged into a #math.equation(block: false, alt: "1 times 2")[$1 × 2$] rectangle,
        and we require #math.equation(block: false, alt: "2 minus 1 equals 1")[$2 − 1 = 1$] breaks to reduce this to single squares.


        Inductive case:
        Fix an arbitrary #math.equation(block: false, alt: "n greater than or equal to 2")[$n ≥ 2$] and assume #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true for all #math.equation(block: false, alt: "k less than n")[$k < n$].
        Consider a #math.equation(block: false, alt: "n")[$n$]-square rectangular chocolate bar.
        Break the bar once along any row or column.
        This results in two chocolate bars,
        say of sizes #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$].
        That is, we have an #math.equation(block: false, alt: "a")[$a$]-square rectangular chocolate bar,
        a #math.equation(block: false, alt: "b")[$b$]-square rectangular chocolate bar, and #math.equation(block: false, alt: "a plus b equals n")[$a + b = n$].


        We also know that #math.equation(block: false, alt: "a less than n")[$a < n$] and #math.equation(block: false, alt: "b less than n")[$b < n$],
        so by our inductive hypothesis,
        #math.equation(block: false, alt: "P open parenthesis a close parenthesis")[$P ( a )$] and #math.equation(block: false, alt: "P open parenthesis b close parenthesis")[$P ( b )$] are true.
        To reduce the #math.equation(block: false, alt: "a")[$a$]-square bar to single squares takes #math.equation(block: false, alt: "a minus 1")[$a − 1$] breaks;
        to reduce the #math.equation(block: false, alt: "b")[$b$]-square bar to single squares takes #math.equation(block: false, alt: "b minus 1")[$b − 1$] breaks.
        Doing this results in our original bar being reduced to single squares.
        All together it took the initial break,
        plus the #math.equation(block: false, alt: "a minus 1")[$a − 1$] and #math.equation(block: false, alt: "b minus 1")[$b − 1$] breaks,
        for a total of #math.equation(block: false, alt: "1 plus a minus 1 plus b minus 1 equals a plus b minus 1 equals n minus 1")[$1 + a − 1 + b − 1 = a + b − 1 = n − 1$] breaks.
        Thus #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true.


        Therefore, by strong induction,
        #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 2")[$n ≥ 2$].
]


      Here is a more mathematically relevant example:


      #examplebox("Example 4")[][
Prove that any natural number greater than 1 is either prime
              
          or can be written as the product of primes.


        
        #solutionbox[
First, the idea:
          if we take some number #math.equation(block: false, alt: "n")[$n$], maybe it is prime.
          If so, we are done.
          If not, then it is composite,
          so it is the product of two smaller numbers.
          Each of these factors is smaller than #math.equation(block: false, alt: "n")[$n$]
          (but at least 2),
          so we can repeat the argument with these numbers.
          We have reduced to a smaller case.


          Now the formal proof:


          #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement,
            “#math.equation(block: false, alt: "n")[$n$] is either prime or can be written as the product of primes.”
            We will prove #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 2")[$n ≥ 2$].


            Base case: #math.equation(block: false, alt: "P open parenthesis 2 close parenthesis")[$P ( 2 )$] is true because #math.equation(block: false, alt: "2")[$2$] is indeed prime.


            Inductive case: assume #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true for all #math.equation(block: false, alt: "k less than n")[$k < n$].
            We want to show that #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true.
            That is, we want to show that #math.equation(block: false, alt: "n")[$n$] is either prime or is the product of primes.
            If #math.equation(block: false, alt: "n")[$n$] is prime, we are done.
            If not, then #math.equation(block: false, alt: "n")[$n$] has more than 2 divisors,
            so we can write #math.equation(block: false, alt: "n equals m sub 1 times m sub 2")[$n = m_(1) ⋅ m_(2)$],
            with #math.equation(block: false, alt: "m sub 1")[$m_(1)$] and #math.equation(block: false, alt: "m sub 2")[$m_(2)$] less than #math.equation(block: false, alt: "n")[$n$]
            (and greater than 1).
            By the inductive hypothesis,
            #math.equation(block: false, alt: "m sub 1")[$m_(1)$] and #math.equation(block: false, alt: "m sub 2")[$m_(2)$] are each either prime or can be written as the product of primes.
            In either case,
            we have that #math.equation(block: false, alt: "n")[$n$] is written as the product of primes.


            Thus by the strong induction,
            #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 2")[$n ≥ 2$].
]
]
]


      Whether you use regular induction or strong induction depends on the statement you want to prove.
      If you wanted to be safe, you could always use strong induction.
      It really is #emph[stronger],
      so can accomplish everything “weak” induction can.
      
      That said, using regular induction is often easier since there is only one place you can use the induction hypothesis.
      There is also something to be said for
      #emph[elegance] in proofs.
      If you can prove a statement using simpler tools, it is nice to do so.


      As a final contrast between the two forms of induction,
      consider once more the stamp problem.
      Regular induction worked by showing how to increase postage by one cent
      (either replacing three 5-cent stamps with two 8-cent stamps,
      or three 8-cent stamps with five 5-cent stamps).
      We could give a slightly different proof using strong induction.
      First, we could show #emph[five] base cases:
      it is possible to make 28, 29, 30, 31, and 32 cents
      (we would actually say how each of these is made).
      Now assume that it is possible to make #math.equation(block: false, alt: "k")[$k$] cents of postage for all #math.equation(block: false, alt: "k less than n")[$k < n$] as long as #math.equation(block: false, alt: "k greater than or equal to 28")[$k ≥ 28$].
      As long as #math.equation(block: false, alt: "n greater than 32")[$n > 32$],
      this means in particular we can make #math.equation(block: false, alt: "k equals n minus 5")[$k = n − 5$] cents.
      Now add a 5-cent stamp to get make #math.equation(block: false, alt: "n")[$n$] cents.


    
    
      
        On the way to the market,
        you exchange your cow for some magic dark chocolate espresso beans.
        These beans have the property that every night at midnight,
        each bean splits into two, effectively doubling your collection.
        You decide to take advantage of this and each morning (around 8am) you eat 5 beans.


        + Explain why it is true that #emph[if]
              at noon on day #math.equation(block: false, alt: "n")[$n$] you have a number of beans ending in a 5, then at noon on day #math.equation(block: false, alt: "n plus 1")[$n + 1$] you will still have a number of beans ending in a 5.
+ Why is the previous fact not enough to conclude that you will always have a number of beans ending in a 5?
              What additional fact would you need?
+ Assuming you have the additional fact in part (b),
              and have successfully proved the fact in part (a),
              how do you know that you will always have a number of beans ending in a 5?
              Illustrate what is going on by carefully explaining how the two facts above prove that you will have a number of beans ending in a 5 on
              #emph[day 4] specifically.
              In other words, explain why induction works in this context.


        #solutionbox[
+ If we have a number of beans ending in a 5 and we double it,
              we will get a number of beans ending in a 0
              (since #math.equation(block: false, alt: "5 times 2 equals 10")[$5 ⋅ 2 = 10$] ).
              Then if we subtract 5, we will once again get a number of beans ending in a 5.
              Thus if on any day we have a number ending in a 5, the next day will also have a number ending in a 5.
+ If you don't #emph[start] with a number of beans ending in a 5
              (on day 1),
              the above reasoning is still correct but not helpful.
              For example,
              if you start with a number ending in a 3, the next day you will have a number ending in a 1.
+ Part (b) is the base case and part (a) is the inductive case.
              If on day 1 we have a number ending in a 5 (by part (b)),
              then on day 2 we will also have a number ending in a 5 (by part (a)).
              Then by part (a) again, we will have a number ending in a 5 on day 3.
              By part (a) again,
              this means we will have a number ending in a 5 on day 4
             #linebreak() 
              The proof by induction would say that on #emph[every]
              day we will have a number ending in a 5, and this works because we can start with the base case,
              then use the inductive case over and over until we get up to our desired #math.equation(block: false, alt: "n")[$n$].
]


      
      
        Use induction to prove for all
        #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$] that #math.equation(block: false, alt: "∑ k equals 0 n 2 to the power k equals 2 to the power n plus 1 minus 1")[$display(limits(∑)^(n)_(k = 0) 2^(k) = 2^(n + 1) − 1)$].


        #solutionbox[
#notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
We must prove that #math.equation(block: false, alt: "1 plus 2 plus 2 squared plus 2 cubed plus ⋯ plus 2 to the power n equals 2 to the power n plus 1 minus 1")[$1 + 2 + 2^(2) + 2^(3) + ⋯ + 2^(n) = 2^(n + 1) − 1$] for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
          Thus let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement #math.equation(block: false, alt: "1 plus 2 plus 2 squared plus ⋯ plus 2 to the power n equals 2 to the power n plus 1 minus 1")[$1 + 2 + 2^(2) + ⋯ + 2^(n) = 2^(n + 1) − 1$].
          We will prove that #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
          First we establish the base case,
          #math.equation(block: false, alt: "P open parenthesis 0 close parenthesis")[$P ( 0 )$], which claims that #math.equation(block: false, alt: "1 equals 2 to the power 0 plus 1 minus 1")[$1 = 2^(0 + 1) − 1$].
          Since #math.equation(block: false, alt: "2 to the power 1 minus 1 equals 2 minus 1 equals 1")[$2^(1) − 1 = 2 − 1 = 1$],
          we see that #math.equation(block: false, alt: "P open parenthesis 0 close parenthesis")[$P ( 0 )$] is true.
          Now for the inductive case.
          Assume that #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true for an arbitrary #math.equation(block: false, alt: "k ∈ N")[$k ∈ N$].
          That is, #math.equation(block: false, alt: "1 plus 2 plus 2 squared plus ⋯ plus 2 to the power k equals 2 to the power k plus 1 minus 1")[$1 + 2 + 2^(2) + ⋯ + 2^(k) = 2^(k + 1) − 1$].
          We must show that #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true (i.e., that #math.equation(block: false, alt: "1 plus 2 plus 2 squared plus ⋯ plus 2 to the power k plus 1 equals 2 to the power k plus 2 minus 1")[$1 + 2 + 2^(2) + ⋯ + 2^(k + 1) = 2^(k + 2) − 1$]).
          To do this, we start with the left-hand side of #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] and work to the right-hand side:


            #math.equation(block: true, alt: "1 plus 2 plus 2 squared plus ⋯ plus 2 to the power k plus 2 to the power k plus 1 equals, 2 to the power k plus 1 minus 1 plus 2 to the power k plus 1, by inductive hypothesis; equals, 2 times 2 to the power k plus 1 minus 1; equals, 2 to the power k plus 2 minus 1")[$1 + 2 + 2^(2) + ⋯ + 2^(k) + 2^(k + 1) = & " " 2^(k + 1) − 1 + 2^(k + 1) & "by inductive hypothesis" \ = & " " 2 ⋅ 2^(k + 1) − 1 &  \ = & " " 2^(k + 2) − 1 &$]
            Thus #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true so by the principle of mathematical induction,
          #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
]
]


      
      
        Prove that #math.equation(block: false, alt: "7 to the power n minus 1")[$7^(n) − 1$] is a multiple of 6 for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].


        #solutionbox[
#notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement
          “#math.equation(block: false, alt: "7 to the power n minus 1")[$7^(n) − 1$] is a multiple of 6.”
          We will show #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
          First we establish the base case, #math.equation(block: false, alt: "P open parenthesis 0 close parenthesis")[$P ( 0 )$].
          Since #math.equation(block: false, alt: "7 to the power 0 minus 1 equals 0")[$7^(0) − 1 = 0$],
          and #math.equation(block: false, alt: "0")[$0$] is a multiple of 6, #math.equation(block: false, alt: "P open parenthesis 0 close parenthesis")[$P ( 0 )$] is true.
          Now for the inductive case.
          Assume #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] holds for an arbitrary #math.equation(block: false, alt: "k ∈ N")[$k ∈ N$].
          That is, #math.equation(block: false, alt: "7 to the power k minus 1")[$7^(k) − 1$] is a multiple of 6, or in other words,
          #math.equation(block: false, alt: "7 to the power k minus 1 equals 6 j")[$7^(k) − 1 = 6 j$] for some integer #math.equation(block: false, alt: "j")[$j$].
          Now consider #math.equation(block: false, alt: "7 to the power k plus 1 minus 1")[$7^(k + 1) − 1$]:


            #math.equation(block: true, alt: "7 to the power k plus 1 minus 1, equals 7 to the power k plus 1 minus 7 plus 6, by cleverness: minus 1 equals minus 7 plus 6; equals 7 open parenthesis 7 to the power k minus 1 close parenthesis plus 6, factor out a 7 from the first two terms; equals 7 open parenthesis 6 j close parenthesis plus 6, by the inductive hypothesis; equals 6 open parenthesis 7 j plus 1 close parenthesis, factor out a 6")[$7^(k + 1) − 1 " " & = 7^(k + 1) − 7 + 6 & "by cleverness:" − 1 = − 7 + 6 \  & = 7 ( 7^(k) − 1 ) + 6 & "factor out a 7 from the first two terms" \  & = 7 ( 6 j ) + 6 & "by the inductive hypothesis" \  & = 6 ( 7 j + 1 ) & "factor out a 6"$]
            Therefore #math.equation(block: false, alt: "7 to the power k plus 1 minus 1")[$7^(k + 1) − 1$] is a multiple of 6, or in other words,
          #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true.
          Therefore by the principle of mathematical induction,
          #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
]
]


      
      
        Prove that #math.equation(block: false, alt: "1 plus 3 plus 5 plus ⋯ plus open parenthesis 2 n minus 1 close parenthesis equals n squared")[$1 + 3 + 5 + ⋯ + ( 2 n − 1 ) = n^(2)$] for all #math.equation(block: false, alt: "n greater than or equal to 1")[$n ≥ 1$].


        #solutionbox[
#notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement #math.equation(block: false, alt: "1 plus 3 plus 5 plus ⋯ plus open parenthesis 2 n minus 1 close parenthesis equals n squared")[$1 + 3 + 5 + ⋯ + ( 2 n − 1 ) = n^(2)$].
          We will prove that #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 1")[$n ≥ 1$].
          First the base case, #math.equation(block: false, alt: "P open parenthesis 1 close parenthesis")[$P ( 1 )$].
          We have #math.equation(block: false, alt: "1 equals 1 squared")[$1 = 1^(2)$] which is true,
          so #math.equation(block: false, alt: "P open parenthesis 1 close parenthesis")[$P ( 1 )$] is established.
          Now the inductive case.
          Assume that #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true for some fixed arbitrary #math.equation(block: false, alt: "k greater than or equal to 1")[$k ≥ 1$].
          That is, #math.equation(block: false, alt: "1 plus 3 plus 5 plus ⋯ plus open parenthesis 2 k minus 1 close parenthesis equals k squared")[$1 + 3 + 5 + ⋯ + ( 2 k − 1 ) = k^(2)$].
          We will now prove that #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is also true (i.e., that #math.equation(block: false, alt: "1 plus 3 plus 5 plus ⋯ plus open parenthesis 2 k plus 1 close parenthesis equals open parenthesis k plus 1 close parenthesis squared")[$1 + 3 + 5 + ⋯ + ( 2 k + 1 ) = ( k + 1 )^(2)$]).
          We start with the left-hand side of #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] and work to the right-hand side:


            #math.equation(block: true, alt: "1 plus 3 plus 5 plus ⋯ plus open parenthesis 2 k minus 1 close parenthesis plus open parenthesis 2 k plus 1 close parenthesis, equals k squared plus open parenthesis 2 k plus 1 close parenthesis, by ind. hyp.; equals open parenthesis k plus 1 close parenthesis squared, by factoring")[$1 + 3 + 5 + ⋯ + ( 2 k − 1 ) + ( 2 k + 1 ) " " & = k^(2) + ( 2 k + 1 ) & "by ind. hyp." \  & = ( k + 1 )^(2) & "by factoring"$]
            Thus #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] holds,
          so by the principle of mathematical induction,
          #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 1")[$n ≥ 1$].
]
]


      
      
        Prove that #math.equation(block: false, alt: "F sub 0 plus F sub 2 plus F sub 4 plus ⋯ plus F sub 2 n equals F sub 2 n plus 1 minus 1")[$F_(0) + F_(2) + F_(4) + ⋯ + F_(2 n) = F_(2 n + 1) − 1$] where #math.equation(block: false, alt: "F sub n")[$F_(n)$] is the #math.equation(block: false, alt: "n")[$n$]th Fibonacci number.


        #solutionbox[
#notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement #math.equation(block: false, alt: "F sub 0 plus F sub 2 plus F sub 4 plus ⋯ plus F sub 2 n equals F sub 2 n plus 1 minus 1")[$F_(0) + F_(2) + F_(4) + ⋯ + F_(2 n) = F_(2 n + 1) − 1$].
          We will show that #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 0")[$n ≥ 0$].
          First the base case is easy because #math.equation(block: false, alt: "F sub 0 equals 0")[$F_(0) = 0$] and #math.equation(block: false, alt: "F sub 1 equals 1")[$F_(1) = 1$] so #math.equation(block: false, alt: "F sub 0 equals F sub 1 minus 1")[$F_(0) = F_(1) − 1$].
          Now consider the inductive case.
          Assume #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true, that is,
          assume #math.equation(block: false, alt: "F sub 0 plus F sub 2 plus F sub 4 plus ⋯ plus F sub 2 k equals F sub 2 k plus 1 minus 1")[$F_(0) + F_(2) + F_(4) + ⋯ + F_(2 k) = F_(2 k + 1) − 1$].
          To establish #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] we work from left to right:


            #math.equation(block: true, alt: "F sub 0 plus F sub 2 plus ⋯ plus F sub 2 k plus F sub 2 k plus 2, equals F sub 2 k plus 1 minus 1 plus F sub 2 k plus 2, by ind. hyp.; equals F sub 2 k plus 1 plus F sub 2 k plus 2 minus 1; equals F sub 2 k plus 3 minus 1, by recursive def.")[$F_(0) + F_(2) + ⋯ + F_(2 k) + F_(2 k + 2) " " & = F_(2 k + 1) − 1 + F_(2 k + 2) & "by ind. hyp." \  & = F_(2 k + 1) + F_(2 k + 2) − 1 &  \  & = F_(2 k + 3) − 1 & "by recursive def."$]
            Therefore #math.equation(block: false, alt: "F sub 0 plus F sub 2 plus F sub 4 plus ⋯ plus F sub 2 k plus 2 equals F sub 2 k plus 3 minus 1")[$F_(0) + F_(2) + F_(4) + ⋯ + F_(2 k + 2) = F_(2 k + 3) − 1$],
          which is to say #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] holds.
          Therefore by the principle of mathematical induction,
          #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 0")[$n ≥ 0$].
]
]


      
      
        Prove that #math.equation(block: false, alt: "2 to the power n less than n !")[$2^(n) < n !$] for all #math.equation(block: false, alt: "n greater than or equal to 4")[$n ≥ 4$].
        (Recall, #math.equation(block: false, alt: "n ! equals 1 times 2 times 3 times ⋯ times n")[$n ! = 1 ⋅ 2 ⋅ 3 ⋅ ⋯ ⋅ n$].)


        #solutionbox[
#notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement #math.equation(block: false, alt: "2 to the power n less than n !")[$2^(n) < n !$].
          We will show #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 4")[$n ≥ 4$].
          First, we check the base case and see that yes, #math.equation(block: false, alt: "2 to the power 4 less than 4 !")[$2^(4) < 4 !$]
          (as #math.equation(block: false, alt: "16 less than 24")[$16 < 24$])
          so #math.equation(block: false, alt: "P open parenthesis 4 close parenthesis")[$P ( 4 )$] is true.
          Now for the inductive case.
          Assume #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true for an arbitrary #math.equation(block: false, alt: "k greater than or equal to 4")[$k ≥ 4$].
          That is, #math.equation(block: false, alt: "2 to the power k less than k !")[$2^(k) < k !$].
          Now consider #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$]: #math.equation(block: false, alt: "2 to the power k plus 1 less than open parenthesis k plus 1 close parenthesis !")[$2^(k + 1) < ( k + 1 ) !$].
          To prove this,
          we start with the left side and work to the right side.


            #math.equation(block: true, alt: "2 to the power k plus 1, equals 2 times 2 to the power k; less than 2 times k !, by the inductive hypothesis; less than open parenthesis k plus 1 close parenthesis times k !, since k plus 1 greater than 2; equals open parenthesis k plus 1 close parenthesis !")[$2^(k + 1) " " & = 2 ⋅ 2^(k) &  \  & < 2 ⋅ k ! & "by the inductive hypothesis" \  & < ( k + 1 ) ⋅ k ! & " since " k + 1 > 2 \  & = ( k + 1 ) ! &$]
            Therefore #math.equation(block: false, alt: "2 to the power k plus 1 less than open parenthesis k plus 1 close parenthesis !")[$2^(k + 1) < ( k + 1 ) !$] so we have established #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$].
          Thus by the principle of mathematical induction #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 4")[$n ≥ 4$].
]
]


      
      
        Prove, by mathematical induction,
        that #math.equation(block: false, alt: "F sub 0 plus F sub 1 plus F sub 2 plus ⋯ plus F sub n equals F sub n plus 2 minus 1")[$F_(0) + F_(1) + F_(2) + ⋯ + F_(n) = F_(n + 2) − 1$],
        where #math.equation(block: false, alt: "F sub n")[$F_(n)$] is the #math.equation(block: false, alt: "n")[$n$]th Fibonacci number
        (#math.equation(block: false, alt: "F sub 0 equals 0")[$F_(0) = 0$],
        #math.equation(block: false, alt: "F sub 1 equals 1")[$F_(1) = 1$] and #math.equation(block: false, alt: "F sub n equals F sub n minus 1 plus F sub n minus 2")[$F_(n) = F_(n − 1) + F_(n − 2)$]).


      
      
        Zombie Euler and Zombie Cauchy,
        two famous zombie mathematicians,
        have just signed up for Twitter accounts.
        After one day, Zombie Cauchy has more followers than Zombie Euler.
        Each day after that,
        the number of new followers of Zombie Cauchy is exactly the same as the number of new followers of Zombie Euler
        (and neither lose any followers).
        Explain how a proof by mathematical induction can show that on every day after the first day, Zombie Cauchy will have more followers than Zombie Euler.
        That is, explain what the base case and inductive case are,
        and why they together prove that Zombie Cauchy will have more followers on the 4th day.


      
      
        Find the largest number of points which a football team cannot get exactly using just 3-point field goals and 7-point touchdowns
        (ignore the possibilities of safeties,
        missed extra points, and two point conversions).
        Prove your answer is correct by mathematical induction.


        
          It is not possible to score exactly 11 points.  Can you prove that you can score #math.equation(block: false, alt: "n")[$n$] points for any #math.equation(block: false, alt: "n greater than or equal to 12")[$n ≥ 12$]?


        
      
      
        Prove that the sum of #math.equation(block: false, alt: "n")[$n$] squares can be found as follows


        #math.equation(block: true, alt: "1 squared plus 2 squared plus 3 squared plus . . . plus n squared equals the fraction n open parenthesis n plus 1 close parenthesis open parenthesis 2 n plus 1 close parenthesis over 6")[$1^(2) + 2^(2) + 3^(2) + . . . + n^(2) = frac(n ( n + 1 ) ( 2 n + 1 ), 6)$]
        .


      
      
        Prove that the sum of the interior angles of a convex #math.equation(block: false, alt: "n")[$n$]-gon is
        #math.equation(block: false, alt: "open parenthesis n minus 2 close parenthesis times 180 degrees")[$( n − 2 ) ⋅ 180^(∘)$]. (A convex #math.equation(block: false, alt: "n")[$n$]-gon is a polygon with #math.equation(block: false, alt: "n")[$n$] sides for which each interior angle is less than #math.equation(block: false, alt: "180 degrees")[$180^(∘)$].)


        
          Start with #math.equation(block: false, alt: "open parenthesis k plus 1 close parenthesis")[$( k + 1 )$]-gon and divide it up into a #math.equation(block: false, alt: "k")[$k$]-gon and a triangle.


        
      
      
        What is wrong with the following
        “proof” of the “fact”
        that #math.equation(block: false, alt: "n plus 3 equals n plus 7")[$n + 3 = n + 7$] for all values of #math.equation(block: false, alt: "n")[$n$] (besides of course that the thing it is claiming to prove is false)?


        #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement that #math.equation(block: false, alt: "n plus 3 equals n plus 7")[$n + 3 = n + 7$].
          We will prove that #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
          Assume, for induction that #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true.
          That is, #math.equation(block: false, alt: "k plus 3 equals k plus 7")[$k + 3 = k + 7$].
          We must show that #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true.
          Now since #math.equation(block: false, alt: "k plus 3 equals k plus 7")[$k + 3 = k + 7$], add 1 to both sides.
          This gives #math.equation(block: false, alt: "k plus 3 plus 1 equals k plus 7 plus 1")[$k + 3 + 1 = k + 7 + 1$].
          Regrouping #math.equation(block: false, alt: "open parenthesis k plus 1 close parenthesis plus 3 equals open parenthesis k plus 1 close parenthesis plus 7")[$( k + 1 ) + 3 = ( k + 1 ) + 7$].
          But this is simply #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$].
          Thus by the principle of mathematical induction #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
]


        #solutionbox[
The only problem is that we never established the base case.
        Of course, when #math.equation(block: false, alt: "n equals 0")[$n = 0$], #math.equation(block: false, alt: "0 plus 3 not equal to 0 plus 7")[$0 + 3 ≠ 0 + 7$].
]


      
      
        The proof in the previous problem does not work.
        But if we modify the “fact,”
        we can get a working proof.
        Prove that #math.equation(block: false, alt: "n plus 3 less than n plus 7")[$n + 3 < n + 7$] for all values of #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
        You can do this proof with algebra
        (without induction),
        but the goal of this exercise is to write out a valid induction proof.


        #solutionbox[
#notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement that #math.equation(block: false, alt: "n plus 3 less than n plus 7")[$n + 3 < n + 7$].
          We will prove that #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
          First, note that the base case holds: #math.equation(block: false, alt: "0 plus 3 less than 0 plus 7")[$0 + 3 < 0 + 7$].
          Now assume for induction that #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true.
          That is, #math.equation(block: false, alt: "k plus 3 less than k plus 7")[$k + 3 < k + 7$].
          We must show that #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true.
          Now since #math.equation(block: false, alt: "k plus 3 less than k plus 7")[$k + 3 < k + 7$], add 1 to both sides.
          This gives #math.equation(block: false, alt: "k plus 3 plus 1 less than k plus 7 plus 1")[$k + 3 + 1 < k + 7 + 1$].
          Regrouping #math.equation(block: false, alt: "open parenthesis k plus 1 close parenthesis plus 3 less than open parenthesis k plus 1 close parenthesis plus 7")[$( k + 1 ) + 3 < ( k + 1 ) + 7$].
          But this is simply #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$].
          Thus by the principle of mathematical induction #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
]
]


      
      
        Find the flaw in the following “proof” of the “fact”
        that #math.equation(block: false, alt: "n less than 100")[$n < 100$] for every #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].


        #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement #math.equation(block: false, alt: "n less than 100")[$n < 100$].
          We will prove #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
          First we establish the base case:
          when #math.equation(block: false, alt: "n equals 0")[$n = 0$], #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true, because #math.equation(block: false, alt: "0 less than 100")[$0 < 100$].
          Now for the inductive step, assume #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true.
          That is, #math.equation(block: false, alt: "k less than 100")[$k < 100$].
          Now if #math.equation(block: false, alt: "k less than 100")[$k < 100$], then #math.equation(block: false, alt: "k")[$k$] is some number, like 80.
          Of course #math.equation(block: false, alt: "80 plus 1 equals 81")[$80 + 1 = 81$] which is still less than 100.
          So #math.equation(block: false, alt: "k plus 1 less than 100")[$k + 1 < 100$] as well.
          But this is what #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] claims,
          so we have shown that #math.equation(block: false, alt: "P open parenthesis k close parenthesis → P open parenthesis k plus 1 close parenthesis")[$P ( k ) → P ( k + 1 )$].
          Thus by the principle of mathematical induction,
          #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
]


        #solutionbox[
The problem here is that while #math.equation(block: false, alt: "P open parenthesis 0 close parenthesis")[$P ( 0 )$] is true,
        and while #math.equation(block: false, alt: "P open parenthesis k close parenthesis → P open parenthesis k plus 1 close parenthesis")[$P ( k ) → P ( k + 1 )$] for
        #emph[some] values of #math.equation(block: false, alt: "k")[$k$],
        there is at least one value of #math.equation(block: false, alt: "k")[$k$]
        (namely #math.equation(block: false, alt: "k equals 99")[$k = 99$])
        when that implication fails.
        For a valid proof by induction,
        #math.equation(block: false, alt: "P open parenthesis k close parenthesis → P open parenthesis k plus 1 close parenthesis")[$P ( k ) → P ( k + 1 )$] must be true for all values of #math.equation(block: false, alt: "k")[$k$] greater than or equal to the base case.
]


      
      
        While the above proof does not work
        (it better not since the statement it is trying to prove is false!)
        we can prove something similar.
        Prove that there is a strictly increasing sequence #math.equation(block: false, alt: "a sub 1 , a sub 2 , a sub 3 , and so on")[$a_(1) , a_(2) , a_(3) , …$] of numbers
        (not necessarily integers)
        such that #math.equation(block: false, alt: "a sub n less than 100")[$a_(n) < 100$] for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
        (By #strong[strictly increasing]
        we mean #math.equation(block: false, alt: "a sub n less than a sub n plus 1")[$a_(n) < a_(n + 1)$] for all #math.equation(block: false, alt: "n")[$n$].
        So each term must be larger than the last.)


        
          For the inductive step, you can assume you have a strictly increasing sequence up to #math.equation(block: false, alt: "a sub k")[$a_(k)$] where #math.equation(block: false, alt: "a sub k less than 100")[$a_(k) < 100$].  Now you just need to find the next term #math.equation(block: false, alt: "a sub k plus 1")[$a_(k + 1)$] so that #math.equation(block: false, alt: "a sub k less than a sub k plus 1 less than 100")[$a_(k) < a_(k + 1) < 100$].  What should #math.equation(block: false, alt: "a sub k plus 1")[$a_(k + 1)$] be?


        
      
      
        What is wrong with the following
        “proof” of the “fact”
        that for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$],
        the number #math.equation(block: false, alt: "n squared plus n")[$n^(2) + n$] is odd?


        #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement
          “#math.equation(block: false, alt: "n squared plus n")[$n^(2) + n$] is odd.”
          We will prove that #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
          Suppose for induction that #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true,
          that is, that #math.equation(block: false, alt: "k squared plus k")[$k^(2) + k$] is odd.
          Now consider the statement #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$].
          Now #math.equation(block: false, alt: "open parenthesis k plus 1 close parenthesis squared plus open parenthesis k plus 1 close parenthesis equals k squared plus 2 k plus 1 plus k plus 1 equals k squared plus k plus 2 k plus 2")[$( k + 1 )^(2) + ( k + 1 ) = k^(2) + 2 k + 1 + k + 1 = k^(2) + k + 2 k + 2$].
          By the inductive hypothesis,
          #math.equation(block: false, alt: "k squared plus k")[$k^(2) + k$] is odd, and of course #math.equation(block: false, alt: "2 k plus 2")[$2 k + 2$] is even.
          An odd plus an even is always odd,
          so therefore #math.equation(block: false, alt: "open parenthesis k plus 1 close parenthesis squared plus open parenthesis k plus 1 close parenthesis")[$( k + 1 )^(2) + ( k + 1 )$] is odd.
          Therefore by the principle of mathematical induction,
          #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
]


        #solutionbox[
We once again failed to establish the base case:
        when #math.equation(block: false, alt: "n equals 0")[$n = 0$], #math.equation(block: false, alt: "n squared plus n equals 0")[$n^(2) + n = 0$] which is even, not odd.
]


      
      
        Now give a valid proof
        (by induction,
        even though you might be able to do so without using induction)
        of the statement, “for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$],
        the number #math.equation(block: false, alt: "n squared plus n")[$n^(2) + n$] is even.”


        
          For the inductive case, you will need to show that #math.equation(block: false, alt: "open parenthesis k plus 1 close parenthesis squared plus open parenthesis k plus 1 close parenthesis")[$( k + 1 )^(2) + ( k + 1 )$] is even.  Factor this out and locate the part of it that is #math.equation(block: false, alt: "k squared plus k")[$k^(2) + k$].  What have you assumed about that quantity?


        
      
      
        Prove that there is a sequence of positive real numbers
        #math.equation(block: false, alt: "a sub 0 , a sub 1 , a sub 2 , and so on")[$a_(0) , a_(1) , a_(2) , …$] such that the partial sum
        #math.equation(block: false, alt: "a sub 0 plus a sub 1 plus a sub 2 plus ⋯ plus a sub n")[$a_(0) + a_(1) + a_(2) + ⋯ + a_(n)$] is strictly less than #math.equation(block: false, alt: "2")[$2$] for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$].
        Hint: think about how you could define what #math.equation(block: false, alt: "a sub k plus 1")[$a_(k + 1)$] is to make the induction argument work.


        
          This is similar to Exercise, although there you were showing that a sequence had all its terms less than some value, and here you are showing that the sum is less than some value.  But the partial sums forms a sequence, so this is actually very similar.


        
      
      
        Prove that every positive integer is either a power of 2, or can be written as the sum of distinct powers of 2.


        #solutionbox[
The proof will be by strong induction.


          #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement
          “#math.equation(block: false, alt: "n")[$n$] is either a power of 2 or can be written as the sum of distinct powers of 2.”
          We will show that #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 1")[$n ≥ 1$].


            Base case: #math.equation(block: false, alt: "1 equals 2 to the power 0")[$1 = 2^(0)$] is a power of 2, so #math.equation(block: false, alt: "P open parenthesis 1 close parenthesis")[$P ( 1 )$] is true.


            Inductive case: Suppose #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true for all #math.equation(block: false, alt: "k less than n")[$k < n$].
          Now if #math.equation(block: false, alt: "n")[$n$] is a power of 2, we are done.
          If not, let #math.equation(block: false, alt: "2 to the power x")[$2^(x)$] be the largest power of 2 strictly less than #math.equation(block: false, alt: "n")[$n$].
          Consider #math.equation(block: false, alt: "n minus 2 to the power x")[$n − 2^(x)$],
          which is a smaller number, in fact smaller than both #math.equation(block: false, alt: "n")[$n$] and #math.equation(block: false, alt: "2 to the power x")[$2^(x)$].
          Thus #math.equation(block: false, alt: "n minus 2 to the power x")[$n − 2^(x)$] is either a power of 2 or can be written as the sum of distinct powers of 2, but none of them are going to be #math.equation(block: false, alt: "2 to the power x")[$2^(x)$],
          so the together with #math.equation(block: false, alt: "2 to the power x")[$2^(x)$] we have written #math.equation(block: false, alt: "n")[$n$] as the sum of distinct powers of 2.


            Therefore, by the principle of (strong) mathematical induction,
          #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 1")[$n ≥ 1$].
]
]


      
      
        Prove, using strong induction,
        that every natural number is either a Fibonacci number or can be written as the #emph[sum]
        of #emph[distinct] Fibonacci numbers.


        
          As with the previous question, we will want to subtract something from #math.equation(block: false, alt: "n")[$n$] in the inductive step.  There we subtracted the largest power of 2 less than #math.equation(block: false, alt: "n")[$n$].  So what should you subtract here?


          Note, you will still need to take care here that the sum you get from the inductive hypothesis, together with the number you subtracted will be a sum of #emph[distinct] Fibonacci numbers.  In fact, you could prove that the Fibonacci numbers in the sum are non-consecutive!


        
      
      
        Use induction to prove that if #math.equation(block: false, alt: "n")[$n$] people all shake hands with each other,
        that the total number of handshakes is #math.equation(block: false, alt: "the fraction n open parenthesis n minus 1 close parenthesis over 2")[$frac(n ( n − 1 ), 2)$].


        
          We have already proved this without using induction, but looking at it inductively sheds light onto the problem (and is fun).


          The question you need to answer to complete the inductive step is, how many new handshakes take place when a person #math.equation(block: false, alt: "k plus 1")[$k + 1$] enters the room.  Why does adding this give you the correct formula?


        
      
      
        Suppose that a particular real number #math.equation(block: false, alt: "x")[$x$] has the property that #math.equation(block: false, alt: "x plus the fraction 1 over x")[$x + frac(1, x)$] is an integer.
        Prove that #math.equation(block: false, alt: "x to the power n plus the fraction 1 over x to the power n")[$x^(n) + frac(1, x^(n))$] is an integer for all natural numbers #math.equation(block: false, alt: "n")[$n$].


        
          You will need to use strong induction.
        For the inductive case, try multiplying #math.equation(block: false, alt: "open parenthesis x to the power k plus the fraction 1 over x to the power k close parenthesis open parenthesis x plus the fraction 1 over x close parenthesis")[$( x^(k) + frac(1, x^(k)) ) ( x + frac(1, x) )$] and collect which terms together are integers.


        
      
      
        Use induction to prove that #math.equation(block: false, alt: "∑ k equals 0 n open parenthesis the fraction n over k close parenthesis equals 2 to the power n")[$display(limits(∑)^(n)_(k = 0) ( binom(n, k) ) = 2^(n))$].
        That is, the sum of the #math.equation(block: false, alt: "n")[$n$]th row of Pascal's Triangle is #math.equation(block: false, alt: "2 to the power n")[$2^(n)$].


        
          Here's the idea:
        since every entry in Pascal's Triangle is the sum of the two entries above it,
        we can get the #math.equation(block: false, alt: "k plus 1")[$k + 1$]st row by adding up all the pairs of entry from the #math.equation(block: false, alt: "k")[$k$]th row.
        But doing this uses each entry on the #math.equation(block: false, alt: "k")[$k$]th row twice.
        Thus each time we drop to the next row, we double the total.
        Of course, row 0 has sum #math.equation(block: false, alt: "1 equals 2 to the power 0")[$1 = 2^(0)$]
        (the base case).
        Now try to make this precise with a formal induction proof.
        You will use the fact that
        #math.equation(block: false, alt: "open parenthesis the fraction n over k close parenthesis equals open parenthesis the fraction n minus 1 over k minus 1 close parenthesis plus open parenthesis the fraction n minus 1 over k close parenthesis")[$( binom(n, k) ) = ( binom(n − 1, k − 1) ) + ( binom(n − 1, k) )$] for the inductive case.


        
      
      
        Use induction to prove #math.equation(block: false, alt: "open parenthesis the fraction 4 over 0 close parenthesis plus open parenthesis the fraction 5 over 1 close parenthesis plus open parenthesis the fraction 6 over 2 close parenthesis plus ⋯ plus open parenthesis the fraction 4 plus n over n close parenthesis equals open parenthesis the fraction 5 plus n over n close parenthesis")[$( binom(4, 0) ) + ( binom(5, 1) ) + ( binom(6, 2) ) + ⋯ + ( binom(4 + n, n) ) = ( binom(5 + n, n) )$].
        (This is an example of the hockey stick theorem.)


        
          To see why this works, try it on a copy of Pascal's triangle.
        We are adding up the entries along a diagonal,
        starting with the 1 on the left-hand side of the 4th row.
        Suppose we add up the first 5 entries on this diagonal.
        The claim is that the sum is the entry below and to the left of the last of these 5 entries.
        Note that if this is true, and we instead add up the first 6 entries,
        we will need to add the entry one spot to the right of the previous sum.
        But these two together give the entry below them,
        which is below and left of the last of the 6 entries on the diagonal.
        If you follow that, you can see what is going on.
        But it is not a great proof.
        A formal induction proof is needed.


        
      
      
        Use the product rule for logarithms (#math.equation(block: false, alt: "log ⁡ open parenthesis a b close parenthesis equals log ⁡ open parenthesis a close parenthesis plus log ⁡ open parenthesis b close parenthesis")[$log ( a b ) = log ( a ) + log ( b )$]) to prove,
        by induction on #math.equation(block: false, alt: "n")[$n$],
        that #math.equation(block: false, alt: "log ⁡ open parenthesis a to the power n close parenthesis equals n log ⁡ open parenthesis a close parenthesis")[$log ( a^(n) ) = n log ( a )$],
        for all natural numbers #math.equation(block: false, alt: "n greater than or equal to 2")[$n ≥ 2$].


        #solutionbox[
The idea here is that if we take the logarithm of #math.equation(block: false, alt: "a to the power n")[$a^(n)$],
        we can increase #math.equation(block: false, alt: "n")[$n$] by 1 if we multiply by another #math.equation(block: false, alt: "a")[$a$]
        (inside the logarithm).
        This results in adding 1 more #math.equation(block: false, alt: "log ⁡ open parenthesis a close parenthesis")[$log ( a )$] to the total.


          #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement #math.equation(block: false, alt: "log ⁡ open parenthesis a to the power n close parenthesis equals n log ⁡ open parenthesis a close parenthesis")[$log ( a^(n) ) = n log ( a )$].
          The base case, #math.equation(block: false, alt: "P open parenthesis 2 close parenthesis")[$P ( 2 )$] is true,
          because #math.equation(block: false, alt: "log ⁡ open parenthesis a squared close parenthesis equals log ⁡ open parenthesis a times a close parenthesis equals log ⁡ open parenthesis a close parenthesis plus log ⁡ open parenthesis a close parenthesis equals 2 log ⁡ open parenthesis a close parenthesis")[$log ( a^(2) ) = log ( a ⋅ a ) = log ( a ) + log ( a ) = 2 log ( a )$],
          by the product rule for logarithms.
          Now assume, for induction, that #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true.
          That is, #math.equation(block: false, alt: "log ⁡ open parenthesis a to the power k close parenthesis equals k log ⁡ open parenthesis a close parenthesis")[$log ( a^(k) ) = k log ( a )$].
          Consider #math.equation(block: false, alt: "log ⁡ open parenthesis a to the power k plus 1 close parenthesis")[$log ( a^(k + 1) )$].
          We have


            #math.equation(block: true, alt: "log ⁡ open parenthesis a to the power k plus 1 close parenthesis equals log ⁡ open parenthesis a to the power k times a close parenthesis equals log ⁡ open parenthesis a to the power k close parenthesis plus log ⁡ open parenthesis a close parenthesis equals k log ⁡ open parenthesis a close parenthesis plus log ⁡ open parenthesis a close parenthesis")[$log ( a^(k + 1) ) = log ( a^(k) ⋅ a ) = log ( a^(k) ) + log ( a ) = k log ( a ) + log ( a )$]
            ,
          with the last equality due to the inductive hypothesis.
          But this simplifies to #math.equation(block: false, alt: "open parenthesis k plus 1 close parenthesis log ⁡ open parenthesis a close parenthesis")[$( k + 1 ) log ( a )$],
          establishing #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$].
          Therefore by the principle of mathematical induction,
          #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 2")[$n ≥ 2$].
]
]


      
      
        Let #math.equation(block: false, alt: "f sub 1 , f sub 2 , and so on , f sub n")[$f_(1) , f_(2) , … , f_(n)$] be differentiable functions.
        Prove, using induction, that


        #math.equation(block: true, alt: "open parenthesis f sub 1 plus f sub 2 plus ⋯ plus f sub n close parenthesis prime equals f sub 1 to the power ′ plus f sub 2 to the power ′ plus ⋯ plus f sub n to the power ′")[$( f_(1) + f_(2) + ⋯ + f_(n) )^(′) = f_(1)^(′) + f_(2)^(′) + ⋯ + f_(n)^(′)$]
        .


        You may assume #math.equation(block: false, alt: "open parenthesis f plus g close parenthesis prime equals f prime plus g prime")[$( f + g )^(′) = f^(′) + g^(′)$] for any differentiable functions #math.equation(block: false, alt: "f")[$f$] and #math.equation(block: false, alt: "g")[$g$].


        
          You are allowed to assume the base case.
        For the inductive case,
        group all but the last function together as one sum of functions,
        then apply the usual sum of derivatives rule,
        and then the inductive hypothesis.


        
      
      
        Suppose #math.equation(block: false, alt: "f sub 1 , f sub 2 , and so on , f sub n")[$f_(1) , f_(2) , … , f_(n)$] are differentiable functions.
        Use mathematical induction to prove the generalized product rule:


        #math.equation(block: true, alt: "open parenthesis f sub 1 f sub 2 f sub 3 ⋯ f sub n close parenthesis prime equals f sub 1 to the power ′ f sub 2 f sub 3 ⋯ f sub n plus f sub 1 f sub 2 to the power ′ f sub 3 ⋯ f sub n plus f sub 1 f sub 2 f sub 3 to the power ′ ⋯ f sub n plus ⋯ plus f sub 1 f sub 2 f sub 3 ⋯ f sub n to the power ′")[$( f_(1) f_(2) f_(3) ⋯ f_(n) )^(′) = f_(1)^(′) f_(2) f_(3) ⋯ f_(n) + f_(1) f_(2)^(′) f_(3) ⋯ f_(n) + f_(1) f_(2) f_(3)^(′) ⋯ f_(n) + ⋯ + f_(1) f_(2) f_(3) ⋯ f_(n)^(′)$]
        .


        You may assume the product rule for two functions is true.


        
          For the inductive step, we know by the product rule for two functions that


          #math.equation(block: true, alt: "open parenthesis f sub 1 f sub 2 f sub 3 ⋯ f sub k f sub k plus 1 close parenthesis prime equals open parenthesis f sub 1 f sub 2 f sub 3 ⋯ f sub k close parenthesis prime f sub k plus 1 plus open parenthesis f sub 1 f sub 2 f sub 3 ⋯ f sub k close parenthesis f sub k plus 1 to the power ′")[$( f_(1) f_(2) f_(3) ⋯ f_(k) f_(k + 1) )^(′) = ( f_(1) f_(2) f_(3) ⋯ f_(k) )^(′) f_(k + 1) + ( f_(1) f_(2) f_(3) ⋯ f_(k) ) f_(k + 1)^(′)$]
          .


          Then use the inductive hypothesis on the first summand,
        and distribute.


        
      
      
        Here is an example of a more complicated induction technique called
        #strong[double induction].


        You will prove that the Fibonacci numbers satisfy the identity #math.equation(block: false, alt: "F sub n squared plus F sub n plus 1 squared equals F sub 2 n plus 1")[$F_(n)^(2) + F_(n + 1)^(2) = F_(2 n + 1)$].
        One way to do this is to prove the more general identity,


        #math.equation(block: true, alt: "F sub m F sub n plus F sub m plus 1 F sub n plus 1 equals F sub m plus n plus 1")[$F_(m) F_(n) + F_(m + 1) F_(n + 1) = F_(m + n + 1)$]
        ,
        and realize that when #math.equation(block: false, alt: "m equals n")[$m = n$] we get our desired result.


        Note that we now have two variables,
        so we want to prove this for all #math.equation(block: false, alt: "m greater than or equal to 0")[$m ≥ 0$] #emph[and]
        all #math.equation(block: false, alt: "n greater than or equal to 0")[$n ≥ 0$] at the same time.
        For each such pair #math.equation(block: false, alt: "open parenthesis m , n close parenthesis")[$( m , n )$],
        let #math.equation(block: false, alt: "P open parenthesis m , n close parenthesis")[$P ( m , n )$] be the statement #math.equation(block: false, alt: "F sub m F sub n plus F sub m plus 1 F sub n plus 1 equals F sub m plus n plus 1")[$F_(m) F_(n) + F_(m + 1) F_(n + 1) = F_(m + n + 1)$]


        + First fix #math.equation(block: false, alt: "m equals 0")[$m = 0$] and give a proof by mathematical induction that #math.equation(block: false, alt: "P open parenthesis 0 , n close parenthesis")[$P ( 0 , n )$] holds for all #math.equation(block: false, alt: "n greater than or equal to 0")[$n ≥ 0$].
              Note this proof will be very easy.
+ Now fix an arbitrary #math.equation(block: false, alt: "n")[$n$] and give a proof by #emph[strong]
              mathematical induction that #math.equation(block: false, alt: "P open parenthesis m , n close parenthesis")[$P ( m , n )$] holds for all #math.equation(block: false, alt: "m greater than or equal to 0")[$m ≥ 0$].
+ You can now conclude that #math.equation(block: false, alt: "P open parenthesis m , n close parenthesis")[$P ( m , n )$] holds for all #math.equation(block: false, alt: "m , n greater than or equal to 0")[$m , n ≥ 0$].
              Do you believe that?
              Explain why this sort of induction is valid.
              For example,
              why do your proofs above guarantee that #math.equation(block: false, alt: "P open parenthesis 2 , 3 close parenthesis")[$P ( 2 , 3 )$] is true?


      
      
        Given a square,
        you can cut the square into smaller squares by cutting along lines parallel to the sides of the original square
        (these lines do not need to travel the entire side length of the original square).
        For example, by cutting along the lines below,
        you will divide a square into 6 smaller squares:


        #figure(figph[One large square with five squares of half the side length wrapping around the top and right side, forming an even larger square.], alt: "One large square with five squares of half the side length wrapping around the top and right side, forming an even larger square.", caption: none)


        Prove, using strong induction,
        that it is possible to cut a square into #math.equation(block: false, alt: "n")[$n$] smaller squares for any #math.equation(block: false, alt: "n greater than or equal to 6")[$n ≥ 6$].


        
          You will need three base cases.  This is a very good hint actually, as it suggests that to prove #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true, you would want to use the fact that #math.equation(block: false, alt: "P open parenthesis n minus 3 close parenthesis")[$P ( n − 3 )$] is true.  So somehow you need to increase the number of squares by 3.