December 09, 2019, 04:14:13 am

### AuthorTopic: Classic use of mathematical induction  (Read 172 times)

0 Members and 1 Guest are viewing this topic.

#### RuiAce

• ATAR Notes Lecturer
• Moderator
• Great Wonder of ATAR Notes
• Posts: 8614
• "All models are wrong, but some are useful."
• Respect: +2412
##### Classic use of mathematical induction
« on: June 08, 2019, 02:12:33 pm »
+8
Remember to register here for FREE to ask any questions you may come across in your QCE studies!

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 »