Mathematical Induction, Proof, and Recursively Defined Functions

Part A: Mathematical Induction

Mathematical Induction is a proof technique used to prove that a statement $P(n)$ is true for all positive integers $n$. It works like a chain of dominoes — if the first one falls, and each domino knocks the next, then all dominoes fall.

Two Steps of Mathematical Induction:

• Basis Step: Prove that $P(1)$ is true (i.e., the statement holds for $n = 1$).
• Inductive Step: Assume $P(k)$ is true for some arbitrary positive integer $k$ (called the inductive hypothesis). Then prove that $P(k+1)$ is also true.

If both steps are completed, we conclude $P(n)$ is true for all positive integers $n$ by the Principle of Mathematical Induction.

---

Part B: Prove that the sum of first $n$ odd positive integers is $n^2$

Statement: $1 + 3 + 5 + \cdots + (2n-1) = n^2$ for all positive integers $n$.

The i$-th odd positive integer is $(2i - 1), so we need to prove:

$$P(n): \sum_{i=1}^{n} (2i - 1) = n^2$$

Basis Step ($n = 1$):

• LHS $= 2(1) - 1 = 1$
• RHS $= 1^2 = 1$
• LHS $=$ RHS ✓

So $P(1)$ is true.

Inductive Step:

Assume $P(k)$ is true for some positive integer $k$, i.e.,

$$1 + 3 + 5 + \cdots + (2k - 1) = k^2 \quad \text{...(Inductive Hypothesis)}$$

We need to prove $P(k+1)$:

$$1 + 3 + 5 + \cdots + (2k - 1) + (2(k+1) - 1) = (k+1)^2$$

Proof:

Taking LHS of $P(k+1)$:

$$\text{LHS} = \underbrace{1 + 3 + 5 + \cdots + (2k-1)}_{= k^2 \text{ (by inductive hypothesis)}} + (2k + 1)$$

$$= k^2 + 2k + 1$$

$$= (k+1)^2$$

$$= \text{RHS}$$

Since $P(k+1)$ is true whenever $P(k)$ is true, by the Principle of Mathematical Induction, the statement $P(n)$ is true for all positive integers $n$. $\blacksquare$

---

Part C: Recursively Defined Function

A recursively defined function is a function whose value at a given input is defined in terms of its values at smaller inputs, along with explicitly specified initial values.

A recursive definition has two parts:

• Basis Step: Specify the value of the function at the initial point(s), e.g., $f(0)$ or $f(1)$.
• Recursive Step: Give a rule for finding the function's value at an integer from its values at smaller integers.

Example: The factorial function is defined recursively as:

• $f(0) = 1$ (Basis)
• $f(n) = n \cdot f(n-1)$ for $n \geq 1$ (Recursive step)

So, $f(4) = 4 \cdot f(3) = 4 \cdot 3 \cdot 2 \cdot 1 = 24$

---

Conclusion: Mathematical induction is a powerful tool for proving statements about all positive integers, and recursively defined functions allow us to define complex functions elegantly using simpler base cases and self-referencing rules.