9SsSe

Discrete Mathematics Lecture 7 — Induction and Recursion

University course in discrete mathematics for computer science and engineering.

Sep 28, 2021
Downloads ‐ HTML, Markdown, PDF
All Files ‐ Post Files

Mathematical Induction

Basic Setup

  1. You have a predicate \(P(n)\) which depends on a positive integer \(n\).
  2. You want to prove that \(P(n)\) is true for every \(n \in \mathbb{Z}_+ = \{1, 2, 3, ...\}\).

Proof by induction is done in two steps.

  • Step 1 (base case): You have to verify that \(P(1)\) is true.
  • Step 2 (induction step): You have to prove that \(P(n) \Rightarrow P(n + 1)\).

If you have successfully done these steps, then you have proven that \(P(n)\) is true for all \(n \in \mathbb{Z}_+\). This is from the fundemental construction of how the proof works.

Example 1: Prove that for every \(n \geq 1\), that

\[ \sum_{k=1}^n k = \frac{n(n+1)}{2} \]

So we need to formulate a predicate here first. In our case it is very simple. It is simply the equation above.

\[ P(n) : \sum_{k=1}^n k = \frac{n(n+1)}{2} \]

This is a predicate that depends on \(n\).

Step 1: Verify \(P(1)\).

\[ P(1) : \sum_{k=1}^1 k = \frac{1(1+1)}{2} \]

which simplifies to

\[ 1 = 1 \]

Therefore \(P(n)\) is true for \(n=1\).

Step 2: We now have to prove that \(P(n) \Rightarrow P(n+1)\).

What we do now is assume that \(P(n)\) is true. That is to say that

\[ \sum_{k=1}^n k = \frac{n(n+1)}{2} \tag{1} \]

We want to derive that \(P(n+1)\), that is to say derive that

\[ \sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2} \tag{2} \]

Basically derive equation 2 from 1 algebraically.

Left side of (2).

\[ \sum_{k=1}^{n+1} k = \left ( \sum_{k=1}^n k \right ) + (n + 1) \]

According to (1)

\[ \begin{aligned} &= \frac{n(n+1)}{2} + (n + 1) \\ &= \frac{n+1}{2}(n + 2) \\ &= \frac{(n+1)(n+2)}{2} \\ &= \text{Right Side of (2)} \end{aligned} \]

End of proof.

Remember that you can prove this equivalence in a different way which might be nicer/smarter but harder to realize.

Gauss proof:

\[ \begin{aligned} 1 + 2 + ... + n &= S \\ n + (n-1) + ... + 1 &= S \\ \hline n(n+1) &= 2S \\ \Rightarrow S = \frac{n(n+1)}{2} \\ \end{aligned} \]

The basic idea is to add the two infinite series in different orders which makes it easy to see the pattern of why the sum becomes \(\frac{n(n+1)}{2}\).

3rd Way of proving: Consider

\[ \sum_{k=1}^n [(k+1)^2 - k^2] \]

We will now manipulate this sum in two different ways. On one side the sum is telescoping. Which means that you get a lot of cancellation.

\[ \sum_{k=1}^n [(k+1)^2 - k^2] = (2^2 - 1^2) + (3^2 - 2^2) + (4^2 - 3^2) + ... + ((n_1)^2 - n^2) \]

The only thing that does not cancel here is

\[ \begin{aligned} (n+1)^2 - 1^2 &= (n^2 + 2n + 1) - 1 \\ &= n^2 + 2n \\ &= n(n+2) \\ \end{aligned} \]

On the other side

\[ \begin{aligned} \sum_{k=1}^n \left((k+1)^2 - k^2 \right) &= \sum_{k=1}^n (2k+1) \\ &= 2 \left( \sum_{k=1}^n k \right) + \sum_{k=1}^n 1 \\ &= 2 \left( \sum_{k=1}^n k \right ) + n\\ &\Rightarrow 2\left ( \sum_{k=1}^n k \right) + n = n(n+2) \\ &\Rightarrow \sum_{k=1}^n = \frac{n(n+1)}{2} \end{aligned} \]

Power Sums

Obvious

\[ \sum_{k=1}^n k^0 = n \]

Gauss’s Formula.

\[ \sum_{k=1}^n k^1 = \frac{n(n+1)}{2} \]

Prove this.

\[ \sum_{k=1}^n k^2 = \frac{(n(n+1)(2n+1)}{6} \]

\[ \begin{aligned} & 1^2 = 1 \\ & 1^2 + 2^2 = 5 \\ & 1 + 4 + 9 = 14 \\ & 1 + 4 + 9 + 16 = 30 \end{aligned} \]

Verify the formula with induction

Step 1: Verify the base case.

Left hand side

\[ 1 ^2 = 1 \]

Right hand side

\[ \frac{1 \cdot 2 \cdot 3}{6} = 1 \]

They are equal.

Step 2:

Assume that

\[ \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6} \tag{1} \]

We want to derive that

\[ \sum_{k=1}^{n+1} k^2 = \frac{(n+1)(n+2)(2n+3)}{6} \tag{2} \]

Left hand side of (2).

\[ \begin{aligned} \left( \sum_{k=1}^n k^2 \right ) + (n + 1)^2 &= \frac{n(n+1)(2n+1)}{6} + (n + 1)^2 \\ &= \frac{n+1}{6} \left ( n (2n+1) + 6 (n+1) \right) \\ &= \frac{n + 1}{6} \left( 2n^2 + 7n + 6 \right ) \\ &= \frac{n + 1}{6} (2n + 3)(n + 2) \\ &= \text{Right and side of (2)} \end{aligned} \]

Inequalities

Ex: Prove that, for every \(n \geq 1\), the following is true

\[ \sum_{k=1}^n \frac{1}{k} \leq 1 + ln(n) \]

(Tip: You can use \(ln(1 + x) \leq x \forall x \in (0, 1)\))

Step 1: Verify the inequality for the base case \(n=1\).

Left hand side

\[ \sum_{k=1}^1 \frac{1}{k} = \frac{1}{1} = 1 \]

Right hand side

\[ 1 + ln(1) = 1 + 0 = 1 \]

Therefore the left hand side is equal to the right hand side which \(\leq\) covers as a case.

Step 2: Assume that

\[ \sum_{k=1}^n \frac{1}{k} \leq 1 + ln(n) \tag{1} \]

We want to derive that

\[ \sum_{k=1}^{n+1} \frac{1}{k} \leq 1 + ln(n+1) \tag{2} \]

Left hand of (2)

\[ \sum_{k=1}^{n+1} \frac{1}{k} = \sum_{k=1}^n \frac{1}{k} + \frac{1}{n+1} \]

According to (1)

\[ \left ( \sum_{k=1}^n \frac{1}{k} \right ) + \frac{1}{n+1} \leq 1 + ln(n) + \frac{1}{n+1} \]

It is enough to prove that

\[ 1 + ln(n) + \frac{1}{n + 1} \leq 1 + ln(n+1) \]

which is equivalent with

\[ \begin{aligned} \frac{1}{n+1} \leq ln(n+1) - ln(n) & \Leftrightarrow \frac{1}{n+1} \leq ln \left( \frac{n + 1}{n} \right ) \\ & \Leftrightarrow \frac{1}{n+1} \leq ln \left ( 1 + \frac{1}{n} \right ) \end{aligned} \]

But

\[ ln \left ( 1 + \frac{1}{n} \right ) \geq \frac{1}{n} \]

and it is apparent that

\[ \begin{aligned} &\frac{1}{n} \geq \frac{1}{n+1} \\ & \Rightarrow \frac{1}{n+1} \leq ln \left( 1 + \frac{1}{n} \right ) \end{aligned} \]

end of proof.

Divisibility

Prove that for every \(n \in \mathbb{Z}_+\) that \(n^3-n\) is a multiple of 3.

\[ \begin{aligned} & 1^3-1=1-1=0 \\ & 2^3 - 2 = 8 - 2 = 6 \\ & 3^3 - 3 = 27 - 3 = 24 \\ & 4^3 - 4 = 64 - 4 = 60 \end{aligned} \]

Step 1: Verify the base case \(n=1\).

\[ 1^3 - 1 = 1 - 1 = 0 \]

where \(0\) is a multiple of 3.

Step 2: Assume that

\[ 3 | n^3 -n \tag{1} \]

We want to derive that

\[ 3 | (n+1)^3 - (n+1) \tag{2} \]

Now there is no clear way to do this, we actually have to figure out ourselves how to do this, which might be more challenging than the previous examples.

What we can do is

\[ \begin{aligned} (n+1)^3-(n+1) &= (n^3+3n^2+3n+1) - (n+1) \\ &= (n^3-n) + 3(n^2+n) \end{aligned} \]

Now we know that \((n^3-n)\) in

\[ (n^3-n) + 3(n^2+n) \]

is divisible by 3 according to (1). Also that \(3(n^2+n)\) is quite clearly divisible by 3. Therefore the entire expression

\[ (n^3-n) + 3(n^2+n) \]

is divisible by 3.

end of proof.

Note 1:

We can also solve this without induction in the following manner.

\[ n^3-n = n(n^2-1) = n(n+1)(n-1) \]

The important bit in this derivation is

\[ n(n+1)(n-1) \]

What this esentially means is that \(n^3-n\) is equal to a product of three following numbers. Such as 1, 2 and 3. At least one of these numbers will always be a multiple of three. Therefore \(n^3-n\) will always be divisible by 3.

Note 2:

You can easily derive that \(3|n^3-n \forall n \in \mathbb{Z}\). \(n \in \mathbb{Z}_+\) is proven above. \(n=0 : 0^3-0 = 0\), which is now proven.

But what if \(n \in \mathbb{Z}_-\).

\[ \begin{aligned} f(n) &= n^3-n \\ f(-n) &= (-n)^3 - (-n) \\ &= -n^3 + n \\ &= -f(n) \\ \end{aligned} \]

So since

\[ f(-n) = -f(n) \]

then it is still a multiple of three, you have just changed the sign which does not change whether or not it is a multiple of three or not.

But if your thought was to initially prove \(3|n^3-n \forall n \in \mathbb{Z}\).

But you have to be careful here because in induction you need to have a base case. If you are trying to solve for every number in \(\mathbb{Z}\) then you do not have a clear starting number since \(\mathbb{Z}\) goes to negative and positive infinity for integer values.

You can still do induction, but what you have to do is two proofs of inductions.

So for example.

  1. Verify \(P(1)\).
  2. Prove \(P(n) \Rightarrow P(n+1)\).
  3. Prove \(P(n) \Rightarrow P(n-1)\).

step 3 would essentially translate into

\[ P(n) = 3|n^3-n \]

\[ \begin{aligned} P(n-1) &= 3|(n-1)^3-(n-1) \\ &= (n^3-3n^2+3n-1) - (n-1) \\ &= (n^3-n)-3(n^2-n) \end{aligned} \]

Then we can just use the same arguments as before, that is to say that \((n^3-n)\) is per hypothesis divisible by three and that \(3(n^3-n)\) is self evidently divisible by three, therefore the entire expression is divisible by three.

Ex.5: (The base case does not need to be \(n=1\))

Prove that \(n^2 < 2^n\) for \(n \geq ?\).

  • \(n=0 : 0^2 < 2^0\), true
  • \(n=1 : 1^2 < 2^1\), true
  • \(n=2 : 2^2 = 2^2\), false
  • \(n=3 : 3^2 > 2^3\), false
  • \(n=4 : 4^2 = 24\), false
  • \(n=5 : 5^2 < 2^5\), true

Again this is because \(2^n\) will grow faster than \(n^2\) but not be greater everywhere, so we now know that for \(n \geq 5\) is our base case.

Step 1: Verify the base case \(n=5\), which is already verified.

Step 2: Assume that

\[ n^2 < 2^n \tag{1} \]

Derive that

\[ (n+1)^2 < 2^{n+1} \tag{2} \]

But this proof must be wrong if it does not use that \(n \geq 5\) somewhere. Because there are clearly cases where it is not true.

References