notes from Kenneth H. Rosen's Discrete Mathematics and Its Applications, 7th ed. miscellaneous topics in discrete mathematics.

• Induction and recursion

• Induction

First used by Maurolico in 16th century to prove the sum of first n odd positive integers equals n2(TeX formula: n^2) . De Morgan was the first to formalize it in proofs in 1838, and coined the term "mathematical induction".

despite its name, mathematical induction is not an induction. it's a completely deductive argument, although it might seem inductive (because an infinite number of cases are proven automatically).

  1. Basis step: prove that conjecture holds true for first case
  2. Inductive step: prove that if assumed true for an arbitrary case, then the next case must also be true.

In combination, both facts imply that all cases are true. The truth at the basis step "trickles down" to every case by virtue of also proving step 2.

P(1)∧(TeX formula: P(1) \; ∧ )

∀k(P(k)⟹P(k+1))∀kP(k)(TeX formula: \frac{∀k \; (P(k) \implies P(k+1))}{∀k \; P(k)} )

  • assumes well-ordering of set
  • doesn't give new formulas or conjectures, only proves them
  • no insight as to why theorem is true

• Summation equations

• 1+2+3+...

triangular numbers: n∈ℕ;∀n(1+2+…+n=n(n+1)2)n ∈ \mathbb{N} ; ∀n \left( 1+2+ \ldots + n = \frac{n(n+1)}{2} \right)(TeX formula: n ∈ \mathbb{N} ; ∀n \left( 1+2+ \ldots + n = \frac{n(n+1)}{2} \right))

basis step: 1=1(1+1)2=1(TeX formula: 1=\frac{1(1+1)}{2}=1)

inductive step:

1+…+k=k(k+1)2⟹1+…+k+(k+1)=(k+1)((k+1)+1)2=(k+1)(k+2)2k(k+1)2⏟1+…+k+(k+1)=(k+1)(k+2)2k(k+1)+2(k+1)2=k2+k+2k+22=k2+3k+22=(k+1)(k+2)2 \begin{aligned} \ 1+\ldots+k = \frac{k(k+1)}{2} \implies 1+\ldots+k+(k+1) = \frac{(k+1)((k+1)+1)}{2} = \frac{(k+1)(k+2)}{2} \ \underbrace{\frac{k(k+1)}{2}}_{1+\ldots+k}+(k+1) = \frac{(k+1)(k+2)}{2} \ \frac{k(k+1)+2(k+1)}{2} = \frac{k^{2}+k+2 k+2}{2} = \frac{k^{2}+3 k+2}{2} = \frac{(k+1)(k+2)}{2} \end{aligned} (TeX formula: \begin{aligned} \ 1+\ldots+k = \frac{k(k+1)}{2} \implies 1+\ldots+k+(k+1) = \frac{(k+1)((k+1)+1)}{2} = \frac{(k+1)(k+2)}{2} \\ \underbrace{\frac{k(k+1)}{2}}_{1+\ldots+k}+(k+1) = \frac{(k+1)(k+2)}{2} \\ \frac{k(k+1)+2(k+1)}{2} = \frac{k^{2}+k+2 k+2}{2} = \frac{k^{2}+3 k+2}{2} = \frac{(k+1)(k+2)}{2} \end{aligned} )

alternative algebraic proof by child Gauss:

1+2+…+(n−1)+n=(n+1)+…+(n+1)⏟n/2 times =n2(n+1) 1+2+\ldots+(n-1)+n=\underbrace{(n+1)+\ldots+(n+1)}_{n/2 \text { times }}=\frac{n}{2}(n+1) (TeX formula: 1+2+\ldots+(n-1)+n=\underbrace{(n+1)+\ldots+(n+1)}_{n/2 \text { times }}=\frac{n}{2}(n+1) )

• 1+3+5+...

conjecture: ∑i=0n2i+1=[1,4,9,16,25,…]=[12,22,32,42,52,…]=n2∑_{i=0}^n 2 i+1 = [1,4,9,16,25, \ldots] = [1^{2}, 2^{2}, 3^{2}, 4^{2}, 5^{2}, \ldots] = n^{2}(TeX formula: ∑_{i=0}^n 2 i+1 = [1,4,9,16,25, \ldots] = [1^{2}, 2^{2}, 3^{2}, 4^{2}, 5^{2}, \ldots] = n^{2})

basis step: 1=12(TeX formula: 1=1^{2})

inductive step:

1+3+5+…+(2k−1)=k2⟹1+3+…+(2k−1)+(2k+1)=(k+1)21+3+5+…+(2k−1)⏟k2+(2k+1)=(k+1)2k2+(2k+1)=(k+1)2=k2+2k+1 \begin{aligned} \ 1+3+5+\ldots+(2k-1) = k^2 \implies 1+3+\ldots+(2k-1)+(2k+1)=(k+1)^2 \ \underbrace{1+3+5+\ldots+(2k-1)}_{k^2} + (2k+1) = (k+1)^2 \ k^2 + (2k+1) = (k+1)^2 = k^2 + 2k + 1 \end{aligned} (TeX formula: \begin{aligned} \ 1+3+5+\ldots+(2k-1) = k^2 \implies 1+3+\ldots+(2k-1)+(2k+1)=(k+1)^2 \\ \underbrace{1+3+5+\ldots+(2k-1)}_{k^2} + (2k+1) = (k+1)^2 \\ k^2 + (2k+1) = (k+1)^2 = k^2 + 2k + 1 \end{aligned} )

• 1+2+4+8+...

¿ 1+2+22+23+…+2n=2n+1−1(TeX formula: 1+2+2^2+2^3+\ldots+2^n = 2^{n+1} - 1) ?, ∀n(n∈ℕ)(TeX formula: ∀n (n ∈ \mathbb{N}))

basis step: P(0)=02=20+1−1=1(TeX formula: P(0) = 0^2 = 2^{0+1}-1 = 1)

inductive step:

20+21+…+2k=2k+1−1⟹20+21+…+2k+2(k+1)=2k+2−120+21+…+2k⏟2k+1−1+2(k+1)=2k+2−1(2k+1−1)+2(k+1)=2k+2−12(2k+1)−1=2k+2−12k+2−1=2k+2−1 \begin{aligned} \ 2^0 + 2^1 + \ldots + 2^k = 2^{k+1}-1 \implies 2^0 + 2^1 + \ldots + 2^k + 2^(k+1) = 2^{k+2}-1 \ \underbrace{2^0 + 2^1 + \ldots + 2^k}_{2^{k+1}-1} + 2^(k+1) = 2^{k+2}-1 \ (2^{k+1}-1) + 2^(k+1) = 2^{k+2}-1 \ 2(2^{k+1}) - 1 = 2^{k+2} - 1 \ 2^{k+2} - 1 = 2^{k+2} - 1 \end{aligned} (TeX formula: \begin{aligned} \ 2^0 + 2^1 + \ldots + 2^k = 2^{k+1}-1 \implies 2^0 + 2^1 + \ldots + 2^k + 2^(k+1) = 2^{k+2}-1 \\ \underbrace{2^0 + 2^1 + \ldots + 2^k}_{2^{k+1}-1} + 2^(k+1) = 2^{k+2}-1 \\ (2^{k+1}-1) + 2^(k+1) = 2^{k+2}-1 \\ 2(2^{k+1}) - 1 = 2^{k+2} - 1 \\ 2^{k+2} - 1 = 2^{k+2} - 1 \end{aligned} )

• general geometric series

∑j=0narj=a+ar+ar2+…+arn=arn+1−ar−1;r≠1 ∑_{j=0}^{n} a r^{j} = a + ar +ar^{2} + \ldots + ar^{n} = \frac{ar^{n+1}-a}{r-1}; \; r ≠ 1 (TeX formula: ∑_{j=0}^{n} a r^{j} = a + ar +ar^{2} + \ldots + ar^{n} = \frac{ar^{n+1}-a}{r-1}; \; r ≠ 1 )

basis step:

P(0):∑j=00arj=ar0=aar0+1−ar−1=ar1−ar−1=a(r−1)(r−1)=a \begin{aligned} \ P(0): \ ∑_{j=0}^{0} a r^{j} =a r^{0}= a \ \frac{a r^{0+1}-a}{r-1} = \frac{a r^{1}-a}{r-1} = \frac{a(r-1)}{(r-1)} = a \ \end{aligned} (TeX formula: \begin{aligned} \ P(0): \\ ∑_{j=0}^{0} a r^{j} =a r^{0}= a \\ \frac{a r^{0+1}-a}{r-1} = \frac{a r^{1}-a}{r-1} = \frac{a(r-1)}{(r-1)} = a \\ \end{aligned} )

inductive step:

P(k)⟹P(k+1):ar0+ar2+…+ark=ark+1−ar−1⟹ar0+ar1+…+ark⏟ark+1−ar−1+ark+1=ark+2−ar−1ark+1−ar−1+ark+1=ark+2−ar−1ark+1−a+(r−1)(ark+1)=ark+2−aark+1−a+ark+2−ark+1=ark+2−aark+2−a=ark+2−a \begin{aligned} \ P(k) \implies P(k+1): \ ar^{0} + ar^{2}+ \ldots + ar^{k} = \frac{a r^{k+1}-a}{r-1} \; \implies \; \underbrace{ar^{0} + ar^{1} + \ldots + ar^{k}}_{\frac{ar^{k+1}-a}{r-1}} + ar^{k+1} = \frac{ar^{k+2}-a}{r-1} \ \frac{ar^{k+1}-a}{r-1} + ar^{k+1} = \frac{ar^{k+2}-a}{r-1} \ ar^{k+1}-a + (r-1)(ar^{k+1}) = ar^{k+2} - a \ ar^{k+1} - a + ar^{k+2} - ar^{k+1} = ar^{k+2} - a \ ar^{k+2}-a = ar^{k+2}-a \end{aligned} (TeX formula: \begin{aligned} \ P(k) \implies P(k+1): \\ ar^{0} + ar^{2}+ \ldots + ar^{k} = \frac{a r^{k+1}-a}{r-1} \; \implies \; \underbrace{ar^{0} + ar^{1} + \ldots + ar^{k}}_{\frac{ar^{k+1}-a}{r-1}} + ar^{k+1} = \frac{ar^{k+2}-a}{r-1} \\ \frac{ar^{k+1}-a}{r-1} + ar^{k+1} = \frac{ar^{k+2}-a}{r-1} \\ ar^{k+1}-a + (r-1)(ar^{k+1}) = ar^{k+2} - a \\ ar^{k+1} - a + ar^{k+2} - ar^{k+1} = ar^{k+2} - a \\ ar^{k+2}-a = ar^{k+2}-a \end{aligned} )

• Inequalities

• n < 2n

n<2n;∀n∈ℤ+(TeX formula: n<2^n ; \; ∀n ∈ \mathbb{Z}^{+})

P(1):1<21(TeX formula: P(1): 1<2^1)

P(k)⟹P(k+1):(TeX formula: P(k) \implies P(k+1) :)

k<2k⟹k+1<2k+1⟹k⏟+1<2k⏟+1⟹k+1<2k+2k⏟arbitrarily chosen, as long as inequality is preserved⟹k+1<=2(2k)=2k+1 \begin{aligned} \ k<2^k & \implies k+1<2^{k+1} \ & \implies \underbrace{k}+1 < \underbrace{2^k}+1 \ & \implies k+1 < 2^k + \underbrace{2^k} \ & \text{arbitrarily chosen, as long as inequality is preserved} \ & \implies k+1 <= 2 (2^k) = 2^{k+1} \end{aligned} (TeX formula: \begin{aligned} \ k<2^k & \implies k+1<2^{k+1} \\ & \implies \underbrace{k}+1 < \underbrace{2^k}+1 \\ & \implies k+1 < 2^k + \underbrace{2^k} \\ & \text{arbitrarily chosen, as long as inequality is preserved} \\ & \implies k+1 <= 2 (2^k) = 2^{k+1} \end{aligned} )

• 2n < n!

2n<n!;n≥4(TeX formula: 2^n < n! ; \; n ≥ 4)

P(1):24<4!(TeX formula: P(1): 2^4 < 4!)

P(k)⟹P(k+1):(TeX formula: P(k) \implies P(k+1) :)

2k<k!⟹2k+1<(k+1)!2⋅2k<(k+1)!2⋅2k⏟<2⋅k!⏟2⋅2k<(k+1)⏟k!arbitrarily chosen, as long as inequality is preserved2k+1<(k+1)! \begin{aligned} \ 2^k<k! & \implies 2^{k+1}<(k+1)! \ & 2 \cdot 2^k<(k+1)! \ & 2 \cdot \underbrace{2^k}<2 \cdot \underbrace{k!} \ & 2 \cdot 2^k < \underbrace{(k+1)} k! \ & \text{arbitrarily chosen, as long as inequality is preserved} \ & 2^{k+1}<(k+1)! \end{aligned} (TeX formula: \begin{aligned} \\ 2^k<k! & \implies 2^{k+1}<(k+1)! \\ & 2 \cdot 2^k<(k+1)! \\ & 2 \cdot \underbrace{2^k}<2 \cdot \underbrace{k!} \\ & 2 \cdot 2^k < \underbrace{(k+1)} k! \\ & \text{arbitrarily chosen, as long as inequality is preserved} \\ & 2^{k+1}<(k+1)! \end{aligned} )

• Harmonic numbers

the m-th harmonic number, defined by:

Hm=1+12+13+...+1m=∑n=1m1n H_m=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{m}=∑_{n=1}^m \frac{1}{n} (TeX formula: H_m=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{m}=∑_{n=1}^m \frac{1}{n} )

satisfies the following inequality (i.e. partial sums of the harmonic series satisfy it):

H2n≥1+n2 H_{2^n} ≥ 1+\frac{n}{2} (TeX formula: H_{2^n} ≥ 1+\frac{n}{2} )

proof by induction:

P(0):H20=1≥1+02(TeX formula: P(0): H_{2^0}=1 ≥ 1+\frac{0}{2})

p(k)⟹p(k+1):(TeX formula: p(k) \implies p(k+1):)

H2k≥1+k2⟹H2k+1≥1+k+12⟹1+12+...+12k+12k+1+...12k+1≥1+k+12⟹H2k+12k+1+...+12k+1≥1+k+12⟹H2k+12k+1+...+12k+1≥(1+k2)+12k+1+...+12k+1⏟⟹H2k+12k+1+...+12k+1≥(1+k2)+2k(12k+1)⟹H2k+12k+1+...+12k+1≥(1+k2)+12⟹H2k+1≥1+k+12 \begin{aligned} \ H_{2^k} ≥ 1+\frac{k}{2} & \implies H_{2^{k+1}} ≥ 1+\frac{k+1}{2} \ & \implies 1+\frac{1}{2}+...+\frac{1}{2^k}+\frac{1}{2^k+1}+... \frac{1}{2^{k+1}} ≥ 1+\frac{k+1}{2} \ & \implies H_{2^k}+\frac{1}{2^k+1}+...+\frac{1}{2^{k+1}} ≥ 1+\frac{k+1}{2} \ & \implies H_{2^k}+\frac{1}{2^k+1}+...+\frac{1}{2^{k+1}} ≥ \left( 1+\frac{k}{2} \right) + \underbrace{ \frac{1}{2^k+1}+...+\frac{1}{2^{k+1}} } \ & \implies H_{2^k}+\frac{1}{2^k+1}+...+\frac{1}{2^{k+1}} ≥ \left( 1+\frac{k}{2} \right) + 2^k \left( \frac{1}{2^{k+1}} \right) \ & \implies H_{2^k}+\frac{1}{2^k+1}+...+\frac{1}{2^{k+1}} ≥ \left( 1+\frac{k}{2} \right) + \frac{1}{2} \ & \implies H_{2^{k+1}} ≥ 1+\frac{k+1}{2} \end{aligned} (TeX formula: \begin{aligned} \\ H_{2^k} ≥ 1+\frac{k}{2} & \implies H_{2^{k+1}} ≥ 1+\frac{k+1}{2} \\ & \implies 1+\frac{1}{2}+...+\frac{1}{2^k}+\frac{1}{2^k+1}+... \frac{1}{2^{k+1}} ≥ 1+\frac{k+1}{2} \\ & \implies H_{2^k}+\frac{1}{2^k+1}+...+\frac{1}{2^{k+1}} ≥ 1+\frac{k+1}{2} \\ & \implies H_{2^k}+\frac{1}{2^k+1}+...+\frac{1}{2^{k+1}} ≥ \left( 1+\frac{k}{2} \right) + \underbrace{ \frac{1}{2^k+1}+...+\frac{1}{2^{k+1}} } \\ & \implies H_{2^k}+\frac{1}{2^k+1}+...+\frac{1}{2^{k+1}} ≥ \left( 1+\frac{k}{2} \right) + 2^k \left( \frac{1}{2^{k+1}} \right) \\ & \implies H_{2^k}+\frac{1}{2^k+1}+...+\frac{1}{2^{k+1}} ≥ \left( 1+\frac{k}{2} \right) + \frac{1}{2} \\ & \implies H_{2^{k+1}} ≥ 1+\frac{k+1}{2} \end{aligned} )

This also proves that the harmonic series diverges even if it grows slowly (in the order of the natural logarithm), because the integral of the other side of the inequality diverges itself.

(Image "Figure ")
Figure - Blue: the m-th harmonic number (partial sum of harmonics). Green: ln(x) plus the Euler-Mascheroni constant. Red: the other side of the inequality.

• Divisibility

often easier to prove using basic results in number theory.

• Fermat's little theorem

with p=3.

(∀n∈ℕ∧n≠0)3|n3−n(TeX formula: ( \forall n \in \mathbb{N} \wedge n\neq 0) \; 3 | n^{3}-n)

P(1):13−1≡0(mod3)(TeX formula: P(1): 1^3 - 1 ≡ 0 \; (mod \; 3))

P(k)⟹P(k+1):(TeX formula: P(k) \implies P(k+1) :)

3|k3−k⟹3|(k+1)3−(k+1)⇒3|(k3+3k2+3k+1)−(k+1)⇒3|(k3−k)+3(k2+k)⇒(k3−k)+3(k2+k)3≡0(mod3)⇒(k3−k)3≡0(mod3)∧3(k2+k)3≡0(mod3) \begin{aligned} \ 3| k^{3}-k\implies 3| \left( k+1\right)^{3}-\left( k+1\right) \ & \Rightarrow 3 | \left( k^{3}+3k^{2}+3k+1\right) -\left( k+1\right) \ & \Rightarrow 3 | \left( k^{3}-k\right) +3\left( k^{2}+k\right) \ & \Rightarrow \dfrac{\left( k^{3}-k\right) +3\left( k^{2}+k\right) }{3} ≡ 0 \; (mod \; 3) \ & \Rightarrow \dfrac{\left( k^{3}-k\right) }{3} ≡ 0 \; (mod \; 3) ∧ \dfrac{3\left( k^{2}+k\right) }{3} ≡ 0 \; (mod \; 3) \ \end{aligned} (TeX formula: \begin{aligned} \ 3| k^{3}-k\implies 3| \left( k+1\right)^{3}-\left( k+1\right) \\ & \Rightarrow 3 | \left( k^{3}+3k^{2}+3k+1\right) -\left( k+1\right) \\ & \Rightarrow 3 | \left( k^{3}-k\right) +3\left( k^{2}+k\right) \\ & \Rightarrow \dfrac{\left( k^{3}-k\right) +3\left( k^{2}+k\right) }{3} ≡ 0 \; (mod \; 3) \\ & \Rightarrow \dfrac{\left( k^{3}-k\right) }{3} ≡ 0 \; (mod \; 3) ∧ \dfrac{3\left( k^{2}+k\right) }{3} ≡ 0 \; (mod \; 3) \\ \end{aligned} )

The sum of multiples of n (3 in this case) must also be a multiple of n.

• Sets

• power set cardinality