Comprehensive Proofs by Mathematical Induction: Divisibility, Inequalities, and Series

Methodology of Mathematical Induction

Mathematical induction is a rigorous proof technique used to establish the validity of a statement for all natural numbers or a subset of integers starting from a specific base value. The process involves two primary steps:

• The Basis Step (Base Case): Verify that the statement is true for the smallest value of $n$ (e.g., $n = 1$, $n = 3$, or $n = 5$ as defined by the domain).
• The Inductive Step: Assume the statement holds for an arbitrary positive integer $n = k$. This assumption is known as the Inductive Hypothesis. One must then prove that the statement remains true for $n = k + 1$ based on this assumption.
• Conclusion: If both steps are satisfied, the principle of mathematical induction guarantees the statement is true for every appropriate integer $n$.

Divisibility Proofs for Natural Numbers

Mathematical induction is used to prove that specific algebraic expressions are divisible by certain integers for all $n \in N$.

• Divisibility of Powers: Prove that $7^{2n}$ is divisible by $5$ for all natural numbers $n$. (Note: Transcript specifies $72^n$ or $7^{2n}$ as divisible by $5$).
• Sum of Cubic and Linear Terms: Prove that $n^3 + 5n$ is divisible by $3$ for all $n \in N$.
• Powers of 7 with Constants: Prove that $7^{2n} - 1$ is divisible by $48$ for all $n \in N$.
• Differences of Large Powers: Prove that $4^{3n} - 16^n$ is divisible by $27$ for all $n \in N$.
• Sum of Exponential Terms: Prove that the expression $11^{n+1} + 12^{2n+1}$ is divisible by $133$ for all positive integers $n$.
• Divisibility of Polynomial Binomials: For all $n \in N$, prove that the expression $(x + 2y)^{2n} - (x - 2y)^{2n}$ is divisible by:
  • (i) $4y$
  • (ii) $2x$

Inequality Proofs and Range-Specific Induction

Induction can also verify relationship inequalities where one expression remains consistently greater or less than another for a specified range of $n$.

• Linear vs. Exponential Growth: Prove that $5n < 2^n$ for all integers $n \ge 5$ where $n \in N$.
• Quadratic vs. Linear Growth: For values of $n \ge 3$, prove the inequality $n^2 > 3n$.

Summation Identities via Induction

The principle of mathematical induction is the standard method for proving closed-form solutions for finite series.

• Sum of an Arithmetico-Geometric Sequence:$\sum_{i=1}^{n} i \left(\frac{1}{2}\right)^i = 2 - \frac{n+2}{2^{n-1}}$     (Transcribed as: $() = 12 - 4(n + 4) (\frac{1}{2})^n$).

• Sum of Integer and Power Products:$\sum_{i=1}^{n} i \cdot 2^i = 2 + (n - 1)2^{n+1}$

• Sum of Cubed Integers:$\sum_{k=1}^n k^3 = \frac{n^2(n + 1)^2}{4}$

• Series Involving Factorials:$\sum_{k=1}^n \frac{k}{(k+1)!} = 1 - \frac{1}{(n + 1)!}$

• Reciprocal Products (Telescoping Series):$\sum_{i=1}^n \frac{1}{i(i + 1)} = \frac{n}{n + 1}$

• Trigonometric Summation (Cosine Series):$\sum_{k=1}^n \cos(k\theta) = \frac{\sin\left(\frac{n\theta}{2}\right) \cos\left(\frac{(n+1)\theta}{2}\right)}{\sin\left(\frac{\theta}{2}\right)}$     This holds true for $\theta \neq 2m\pi$ where $m \in Z$.

Product Identities and Sequences

Induction verifies the conversion of products (represented by the capital pi notation $\Pi$) into rational or factorial expressions.

• Cosine Scaling Product:$\prod_{k=1}^n \cos\left(\frac{\theta}{2^k}\right) = \frac{\sin(\theta)}{2^n \sin\left(\frac{\theta}{2^n}\right)}$     Condition: $\sin\left(\frac{\theta}{2^n}\right) \neq 0$.

• Fractional Product Sequences:

  • $\prod_{j=1}^n \left(1 - \frac{1}{2j}\right) = \frac{(2n - 1)!!}{2^n n!}$
  • $\prod_{k=1}^n \left(1 + \frac{1}{2k}\right) = \frac{(2n + 1)!!}{2^n n!}$
  • $\prod_{k=1}^n \left(1 + \frac{1}{2k + 1}\right) = \frac{2^n (n + 1)!}{(2n + 1)!!}$

• Factorial Growth Product:$\prod_{i=1}^n \left(1 + \frac{2}{i}\right) = \frac{(n + 3)!}{6n!}$

Advanced Series and Complex Products

• Rational Function Product:$\prod_{j=1}^n \left(1 + \frac{1}{j(j + 2)}\right) = \frac{n+2}{2(n+1)}$     (Derived from transcript section: $(1 + \frac{1}{1\cdot3}) (1 + \frac{1}{2\cdot4}) ... (1 + \frac{1}{n(n+2)}) = \frac{n+2}{2(n+1)}$).

Display the solutions