0
$\begingroup$

My apologies, I couldn't find a proper title for this question, if you do after reading question please edit it.

I read about mathematical induction theory but still I don't see how is it useful? Can anyone please list me some trivial practical usage of it rather than theoretical questions?

I was seeing this example: Prove that $4^n + 15n -1$ is divisible by $9$.

Statement $S(n)$ : $4^n + 15n -1$ is divisible by $9$.

  1. Of course, statement $S(1)$ is true (first case in proving is done)

  2. Now let's assume $S(r) = 4^r + 15r -1$ be divisible by $9$.
    (though I don't understand what is the rationale behind assuming that: just because theory says so?)

  3. We write $S(r^+)\;=\; 4^{r+1} + 15(r+1) -1$
    ... and the proof goes on

I had learned for natural numbers $x+1 = x^+$ , in above 2nd part of proof , does $S(r^+)$ = $S(r) +1$? or what does it mean?

  • 0
    Induction is "useful" to prove statements like your S(n), i.e. propositions that assert a property holds true for *all* naturals. How else do you propose to prove such *universal* statements if not by induction?2012-09-18

2 Answers 2

1

Following Gerry's advice, begin with these Arturo Magidin's and Pete Clark's posts.

Once you are comfortable with the logic of induction, try to come back at your problem and solve it yourself.
Calling $S(n)$ the expression $4^n+15n-1$, you already checked that S(1) is divisible by 9. Then, assuming that $S(k)$ is divisible by 9, you must show that this implies that $S(k+1)$ is also divisible by 9.

Hint: If you have to prove an implication, you must make use of the inductive hypothesis. So, when writing explicitly $S(k+1)$, try to reconstruct the expression of $S(k)$, about which you can already say something relevant (by hypothesis).

P.S.: As you see, there's no need to introduce further notation defining $x^+\equiv x+1$. If you want to do it, however, then $S(n^+)=S(n+1)=4^{n+1}+15(n+1)-1 \neq 4^n+15n = S(n)+1$.

  • 0
    Hagen has already answered to the main issue: remember, in the inductive step you're not proving the validity of the statement, you are proving the validity of the implication $S(k) \Rightarrow S(k+1)$. The reduction of $S(k+1)$ to something "similar" in some way to $S(k)$ is just the condition you have to expect in order to exploit the inductive hypothesis. I'm being vague about the similarity because it can take different forms in different problems. What you'll find out in this one is quite typical of divisibility problems. That said, it can be very hard to actually make the connection.2012-09-18
0

This is how I would do it:

If $S(r) = 4^r + 15r -1$ is divisible by $9$,

then $4S(r) = 4^{r+1} + 60r -4 = S(r+1) +45 r- 18$ is divisible by $9$,

but $45 r- 18$ is divisible by $9$,

so $S(r+1)$ is divisible by $9$.