Enrol now for our new online tutoring program. Learn from the best tutors. Get amazing results. Learn more.

January 19, 2021, 04:52:00 am

AuthorTopic: Classic use of mathematical induction  (Read 614 times)

0 Members and 1 Guest are viewing this topic.

RuiAce

• ATAR Notes Lecturer
• Moderator
• Great Wonder of ATAR Notes
• Posts: 8781
• "All models are wrong, but some are useful."
• Respect: +2548
Classic use of mathematical induction
« on: June 08, 2019, 02:12:33 pm »
+8

Induction is a special type of proof technique mathematicians use. It tends to be used on proofs based off integers, where recursion helps come into play. The structure involves two key steps:
- An initial statement (sometimes known as the base case) - the statement is explicitly proven for the first integer you permit. (Tends to be $n=1$.)
- An inductive step - the statement is first assumed to hold when $n=k$. Under such an assumption, it should then hold for $n=k+1$.

The principle of mathematical induction asserts that then it will hold for all integers you're required to consider.

The syllabus asks for two types of proofs to consider. For both of them, there's an extra subtlety to handle in the inductive step.
- Sums: When stating what to prove when $n=k+1$, you should always state the last two terms in the sum. That makes it more obvious as to how to use the assumption.
- Divisibility: When stating the assumption, make sure that you introduce some other integer! I personally use $M$ a lot. Then, the assumption may need to be used in a rearranged form.

Example: We will show that $4^n + 15n - 1$ is divisible by 9 for all positive integers $n$, using mathematical induction.

Initial statement
Since we're dealing with the positive integers, the first integer to consider is $n=1$. We manually compute the expression when $n=1$:
$4^1 + 15(1) - 1 = 4+15-1 = 18 = 9\times 2$
which is divisible by $9$. So the statement is true when $n=1$.

Inductive step
When we assume the statement holds for $n=k$ (where $k\geq 1$), we're saying that
$4^k + 15k - 1 = 9M$
for some integer $M$. We wish to prove it holds when $n=k+1$, i.e.
$4^{k+1} + 15(k+1) - 1\text{ is divisible by 9.}$
Here, we can use index laws to spot that $4^{k+1} = 4\times 4^k$, and observe that $4^k$ is perhaps the 'ugliest' thing in the assumed statement. So we make that the subject: $\boxed{4^k = 9M - 15k + 1}$ and continue:
\begin{align*}
4^{k+1} + 15(k+1) - 1 &= 4(4^k) + 15k + 14\\
&= 4(9M-15k + 1) + 15k  14\\
&= 36M - 45k+18\\
&= 9(4M - 5k + 2).
\end{align*}
Since we see that 9 can be factorised (and the stuff in the brackets is still an integer), the expression is therefore divisible by 9. Hence the statement holds when $n=k+1$.

As long as we have these two steps, we can conclude by mathematical induction that the expression is divisible by $9$ for every positive integer.
« Last Edit: June 08, 2019, 02:14:46 pm by RuiAce »