Knowledge Bank
About Categories Posts Tags
Knowledge Bank

Contents

Induction and Recursion

 published in Discrete Mathematics (MTH1114)
   705 words   4 minutes 

Mathematical induction is used for proving statements about large sets of thing while a recursive function repeats or uses its own previous term to calculate subsequent terms.

1 Induction

Outline for proof by induction:

  1. Basis Step: Show that P(1) is true.
  2. Inductive Step: Assume P(k) is true for some positive integers k. (This assumption is called the inductive hypothesis.)
  3. Show that P(k + 1) is true.
  4. Conclude that P(n) is true for all positive integers n by mathematical induction.
Examples
  1. Prove the sum of first $n$ odd integers is $n^2$ .i.e. $1 + 3 + 5 + 7 + … + (2n - 1) = n^2$ for all positive integers.
  • Base: $(2(1) - 1) = 1^2$. Hence $P(1)$ is true.
  • Induction: Suppose that $P(k)$ is true, that is $1 + 3 + 5 + 7 + … + (2k - 1) = k^2$.
  • $1 + 3 + 5 + 7 + … + (2k - 1) + (2(k+1) - 1) = 1 + 3 + 5 + 7 + … + (2k - 1) + 2k + 1$.
  • $ = k^2 + 2k + 1$ (by the inductive hypothesis)
  • $ = (k + 1) ^ 2 $
  • We have shown that $P(k+ 1)$ is true if $P(k)$ is true.
  • Therefore, $P(n)$ is true for all natural numbers $n$ by mathematical induction.

  1. Prove $n^3 - n$ is divisible by 3 for all positive integers.
  • Base: $1^3 - 1 = 0$ and 0 is divisible by 3. Thus, $P(1)$ is true.
  • Induction: Suppose that $P(k)$ is true, that is $k^3 - k$ is divisible by 3.
  • $(k+1)^3 - (k+1) = (k^2+2k+1)(k+1) - (k+1)$
  • $= k^3 + k^2 + 2k^2 + 2k + k + 1 - k - 1$
  • $= k^3 + 3k^2 + 2k$
  • $= (k^3 - k) + 3(k^2 + k)$
  • $P(k+1)$ is true by induction hypothesis and by the definition of divisibility.
  • Therefore, $P(n)$ is true for all positive integers $n$ by mathematical induction.

2 Strong Induction

Outline for proof by strong induction:

  1. Basis Step: Show that P(1) is true.
  2. Inductive Step: Assume P(2) ∧ P(3) ∧ … ∧ P(k-1) ∧ P(k) is true
  3. Show that P(k+1) is true.
  4. Conclude that P(n) is true for all positive integers n by strong induction.
Example

Show that if $n$ is a natural number, then $12|(n^4 – n^2)$.

  • Base: $12|(1^4 – 1^2) = 12|(1 - 1) = 0$. We have shown that $P(1)$ is true.
  • Induction: Assume that $P(2) ∧ P(3) ∧ P(4) ∧ P(5) ∧ P(6)$ is true.
  • Let $k ≥ 6$ and assume and that $12|(m^4 – m^2)$ for $1 ≤ m ≤ k$, now we need to prove that $12|((k+1)^4 – (k+1)^2)$ is true.
  • Let $m = k-5$ for which we assume the proposition to be true such that $(m^4 - m^2) = 12a$.
  • $(m+6)^4 – (m+6)^2= (m^4 +24m^3 + 180m^2 + 864m + 1296) – (m^2 + 12m + 36)$
  • $ = (m^4 – m^2) +24m^3 + 180m^2 + 852m + 1260 $
  • $ = 12a +12(2m^3 + 15m^2 + 71m + 105)$ (by the induction hypothesis)
  • $P(k + 1)$ is true, hence we have proven the proposition by strong induction.

3 Recursive definitions

In simple terms, recursion is defining something in terms of itself. A recursive or inductive definition of a function consists of two steps:

  1. Basis Step: Specify the value of the function at initial values. (e.g. f (0) defined)
  2. Recursive Step: Give a rule for finding its value at an integer from its values at smaller integers. (For n > 0, define f(n) in terms of f(0), f(1), … , f(n − 1))
Example

Consider the following recursive definition:

  • $f(0) = 1$
  • $f(n) = 3f(n - 1) + 2$ for $n ≥ 1$. Use this definition to compute $f(1)$, $f(2)$ and $f(3)$.
  1. $f(1) = 3f(0) + 2 = 3(1) + 2 = 5$
  2. $f(2) = 3f(1) + 2 = 3(5) + 2 = 17$
  3. $f(3) = 3f(2) + 2 = 3(17) + 2 = 53$

Some important functions or sequences in mathematics are defined recursively. For example:

  • Factorials
    • $n! = 1$ if $n = 1$
    • $n! = n (n-1)!$ if $n ≥ 1$
  • Fibonacci numbers
    • $F(0) = 0$
    • $F(1) = 1$
    • $F(n) = F(n-1) + F(n-2)$ for $n ≥ 2$
Discrete Mathematics
Updated on 2022-08-27