# Math in Action: Practical Induction with Factorials

## Mastering the Basics of Factorial Induction

Welcome to the world of mathematical induction, where we’ll dive into the practical application of this powerful technique with a specific focus on factorials. You’re in the right place if you’ve ever wondered how to prove mathematical statements involving factorials. In this guide, we’ll unravel the secrets of mastering the basics of factorial induction and showcase how it’s used in real-world problem-solving.

### Understanding Factorial Notation

Before diving into the induction world, let’s get comfortable with factorial notation. Factorials are represented as $n!$ where n is a positive integer. Essentially, $n!$ means multiplying all positive integers from $1$ to $n$ together. For instance, $5!$ equals $5 \times 4 \times 3 \times 2 \times 1$, which equals $120$.

Factorials are the foundation for many mathematical concepts, including combinatorics and induction. Their role in induction lies in their ability to help us establish the truth of statements for all positive integers.

### Introducing Mathematical Induction

Mathematical induction is a powerful method used to prove statements about positive integers. It consists of two key components: the base case and the induction step.

• Base Case: This is where we prove that the statement holds true for the smallest positive integer, usually $1$.
• Induction Step: In this step, we assume that the statement is true for an arbitrary positive integer k and then prove that it must be true for the next positive integer, $k + 1$.

The beauty of induction lies in its recursive nature. If we can prove the base case and the induction step, we’ve essentially proved the statement for all positive integers.

### The Basics of Factorial Induction

Now that we have a grasp of both factorials and induction let’s combine them and explore the basics of factorial induction.

Step 1: Base Case

Consider the statement: “For all positive integers $n$, $n! > n$”.

• Base Case $n = 1$: When $n = 1$, we have $1! = 1$, greater than $1$. So, the base case holds true.

Step 2: Induction Step

Let’s assume the statement holds true for an arbitrary positive integer $k$, i.e., $k! > k$.

• Induction Hypothesis: Assume $k! > k$.

We aim to prove that the statement is also true for $k + 1$, i.e., $(k + 1)! > k + 1$.

• Induction Step: Start with the assumption $k! > k$. Multiply both sides by $(k + 1)(k + 1)! > (k + 1) \times k(k + 1)! > k(k + 1)$

Now, we know that $k > 1$ (since k is a positive integer), which means $k(k + 1)$ is greater than $k + 1$.

So, $(k + 1)! > k + 1$.

### Tips and Strategies

Factorial induction can become quite complex, but fear not; we have some tips to help you navigate through it:

• Work Through Examples: Practice is key. Start with simpler problems and gradually tackle more challenging ones.
• Understand the Base Case: Understand why the base case holds.
• Use Induction Hypothesis: In the induction step, rely on your assumption (induction hypothesis) that the statement is true for $k$.
• Manipulate Inequalities: Factorial induction often involves inequalities. Learn how to manipulate them to prove your point effectively.

### Real-World Applications

Now that you’ve honed your factorial induction skills, you might wonder where this concept applies in the real world. Here are some intriguing areas:

• Computer Science: Analyzing algorithms and time complexity.
• Statistics: Combinatorial problems and probability.
• Physics: Quantum mechanics and particle physics.
• Economics: Modeling economic growth and market behaviour.

By mastering factorial induction, you’re not just conquering a mathematical concept but unlocking doors to various applications in science, technology, and beyond.

## Example 1

Prove that $(2n)! > 2^n (n!)^2$ using mathematical induction for $n \ge 2$.

#### Step 1

Show it is true for $n =2$.
\begin{aligned} \require{AMSsymbols} \require{color} \text{LHS } &= (2 \times 2)! = 24 \\ \text{RHS } &= 2^2 \times (2!) = 8 \\ \text{LHS } &> \text{ RHS} \\ \end{aligned}
$\therefore \text{It is true for } n =2$

#### Step 2

Assume it is true for $n =k$, that is $(2k)! > 2^k (k!)^2.$

#### Step 3

Show it is true for $n =k+1$, that is $(2k+2)! > 2^{k+1} \big[(k+1)!\big]^2.$
\begin{aligned} \require{color} \text{LHS } &= (2k+2)! \\ &= (2k+2)(2k+1)(2k)! \\ &= 2(k+1)(2k+1)(2k)! \\ &> 2(k+1)(2k+1)2^k (k!)^2 &\color{red} \text{by assumption} \\ &> (k+1)(2k+1)2^{k+1} (k!)^2 \\ &> (k+1)(k+1)2^{k+1} (k!)^2 &\color{red} 2k+1>k+1 \\ &= 2^{k+1} \big[(k+1)k!\big]^2 \\ &= 2^{k+1} \big[(k+1)!\big]^2 \\ &= \text{RHS} \end{aligned}
$\therefore (2k+2)! > 2^{k+1} \big[(k+1)!\big]^2 \text{ for } \ge 2.$

## Example 2

Prove $2 \times 1! + 5 \times 2! + 10 \times 3! + \cdots + (n^2+1)n! = n(n+1)!$.

#### Step 1

Show it is true for $n=1$.

\begin{align} &\text{LHS} = (1^2+1) \times 1! = 2 \\ &\text{RHS} = 1 \times (1+1)! = 2 \\ &\text{LHS} = \text{RHS} \\ &\text{Therefore it is true for } n=1 \end{align}

#### Step 2

Assume that it is true for $n=k$, that is, $2 \times 1! + 5 \times 2! + 10 \times 3! + \cdots + (k^2+1)k! = k(k+1)!$

#### Step 3

Show it is true for $n=k+1$, that is, $2 \times 1! + \cdots + (k^2+1)k! + (k^2+2k+2)(k+1)! = (k+1)(k+2)!$

\begin{align} \text{LHS} &= 2 \times 1! + \cdots + (k^2+1)k! + (k^2+2k+2)(k+1)! \\ &= k(k+1)!+(k^2+2k+2)(k+1)! \\ &= \left[k+\left(k^2+2k+2\right) \right](k+1)! \\ &= \left(k^2+3k+2\right)(k+1)! \\ &= (k+1)(k+2)(k+1)! \\ &= (k+1)(k+2)! \\ &= \text{RHS} \end{align}

Therefore, it is true for $n=k+1$.

Therefore, the statement is true for all integers $n \ge 1$.

## Example 3

Prove by mathematical induction that for all integers $n \ge 1$ ,
$\dfrac{1}{2!} + \dfrac{2}{3!} + \dfrac{3}{4!} + \cdots + \dfrac{n}{(n+1)!} = 1-\dfrac{1}{(n+1)!}$

#### Step 1

Show it is true for $n=1$.
\begin{align} \displaystyle \text{LHS } &= \dfrac{1}{2!} = \dfrac{1}{2} \\ \text{RHS } &= 1-\dfrac{1}{2!} \\ &= 1-\dfrac{1}{2} \\ &= \dfrac{1}{2} \end{align}
Thus, the statement is true for $n=1$.

#### Step 2

Assume the statement is true for $n=k$, that is;
$\dfrac{1}{2!} + \dfrac{2}{3!} + \dfrac{3}{4!} + \cdots + \dfrac{k}{(k+1)!} = 1-\dfrac{1}{(k+1)!}$

#### Step 3

Show the statement is true for $n=k+1$, that is;
$\dfrac{1}{2!} + \dfrac{2}{3!} + \dfrac{3}{4!} + \cdots + \dfrac{k}{(k+1)!} + \dfrac{k+1}{(k+2)!} = 1-\dfrac{1}{(k+2)!}$
\begin{align} \displaystyle \text{LHS } &= \dfrac{1}{2!} + \dfrac{2}{3!} + \dfrac{3}{4!} + \cdots + \dfrac{k}{(k+1)!} + \dfrac{k+1}{(k+2)!} \\ &= 1-\dfrac{1}{(k+1)!} + \dfrac{k+1}{(k+2)!} \\ &= 1-\dfrac{k+2}{(k+2)(k+1)!} + \dfrac{k+1}{(k+2)!} \\ &= 1-\dfrac{k+2}{(k+2)!} + \dfrac{k+1}{(k+2)!} \\ &= 1-\bigg[\dfrac{k+2}{(k+2)!}-\dfrac{k+1}{(k+2)!}\bigg] \\ &= 1-\dfrac{1}{(k+2)!} \\ &= \text{RHS} \end{align}
Therefore, the statement is true for all integers $n \ge 1$ by mathematical induction.

## Interactive Question

### Conclusion

As we conclude our journey through practical factorial induction, remember that this technique isn’t just about math; it’s about problem-solving and critical thinking. Whether you’re a student aiming to ace math exams or an enthusiast delving into the wonders of induction, mastering the basics of factorial induction is a valuable skill. Keep practising, keep exploring, and keep discovering. Math in action is a journey worth taking!

## Induction Made Simple: The Ultimate Guide

“Induction Made Simple: The Ultimate Guide” is your gateway to mastering the art of mathematical induction, demystifying a powerful tool in mathematics. This ultimate guide…

## Induction Magic: Your Ticket to Inequality Triumph

Welcome to the world of mathematical induction, where we unravel the secrets of inequalities. Inequalities can be quite intimidating, but fear not! We have a…

## Math Wizardry: Divisibility and Induction Made Simple

Welcome to the world of math wizardry, where we’ll unravel the secrets of divisibility and induction, making complex concepts remarkably simple. In this article, we’ll…

## Mastering Probability: Venn Diagrams Made Easy

Visualising multiple events using Venn diagrams to find probabilities is done quite often. Welcome to this comprehensive guide on mastering probability using Venn Diagrams. Whether…

Welcome to the fascinating world of probability, where we’ll demystify one essential concept: Replacement in Probability. Whether you’re a student grappling with math problems or…

#### Responses

1. In Example (1) why does (2k+1) become (k+1) in line 6 ?

Thanks

1. Hi Helen.

Please note than (2k+1) is always greater than (k+1) for n > 2.
That is, (2k+1) > (k+1)
-> (2k+1) > (k+1)

Hope this makes sense. Please feel free to let su know if you have further questions.

2. In example 1, step 1, the LHS is (2×2)! = 4!. The factorial of 4 is 1x2x3x4 = 24.

1. You are quite correct. It has been rectified. Thank you!