9
$\begingroup$

Prove that for all natural numbers statement n, statement is dividable by 7

$$15^n+6$$

Base. We prove the statement for $n = 1$

15 + 6 = 21 it is true

Inductive step.

Induction Hypothesis. We assume the result holds for $k$. That is, we assume that

$15^k+6$

is divisible by 7

To prove: We need to show that the result holds for $k+1$, that is, that

$15^{k+1}+6=15^k\cdot 15+6$

and I don't know what to do

$\endgroup$
  • 3
    $\begingroup$ If you have a problem actually writing down the inductive argument, take a look at Arturo's good general advice in this post and try and apply it to your problem: math.stackexchange.com/questions/19370/… $\endgroup$ – Derek Jennings Feb 16 '11 at 12:41
  • $\begingroup$ @Derek Jennings: Like this? $\endgroup$ – Templar Feb 16 '11 at 12:55
  • 1
    $\begingroup$ @Templar: Let's say it's heading in the right direction but it would not be accepted as a full answer as you have not finished off the inductive step using the induction hypothesis, though no doubt you can do this since you've accepted Apostolos's answer. Remark: induction is overkill for this problem since $15 \equiv 1 \pmod{7}$ and so $15^n \equiv 1 \pmod{7}.$ $\endgroup$ – Derek Jennings Feb 16 '11 at 18:45
  • $\begingroup$ @Derek: I agree that congruence considerations give a shorter and more insightful solution than induction. Whether induction is overkill depends upon how comfortable the student is with congruence arguments (and, for instance, whether s/he knows the concept of congruence at all). I recently taught a "transitions" course that covered both of these topics, and a lot of my students were -- surprisingly to me -- more comfortable with the induction argument. $\endgroup$ – Pete L. Clark Feb 16 '11 at 22:59
  • $\begingroup$ (The point, I guess, is that congruences are more abstract than induction. Some people are better at problem solving than thinking abstractly; others the reverse...) $\endgroup$ – Pete L. Clark Feb 16 '11 at 23:00
16
$\begingroup$

Observe that $14$ is divisible by 7. Then let $15^k\cdot 15+6=15^k\cdot 14+ 15^k+6$.

$\endgroup$
6
$\begingroup$

By induction hypothesis, you have $15^k=7t-6$.

$\endgroup$
  • $\begingroup$ Could you explain more about it? $\endgroup$ – Templar Feb 16 '11 at 12:46
  • $\begingroup$ @Templar: $15^{k+1}+6=15^k\cdot 15+6 = (7t-6)\cdot 15+6=7\cdot 15t-90+6=7(15t-12)$ $\endgroup$ – lhf Feb 16 '11 at 12:49
  • $\begingroup$ So you just guess that $15^k=7t-6$ and then prove that is true, right? $\endgroup$ – Templar Feb 16 '11 at 13:02
  • 1
    $\begingroup$ @Templar: No, the induction hypothesis says that $15^k+6$ is a multiple of $7$. So $15^k+6=7t$ for some integer $t$. $\endgroup$ – lhf Feb 16 '11 at 13:04
  • $\begingroup$ Ah, I got it, thanks $\endgroup$ – Templar Feb 16 '11 at 13:07
5
$\begingroup$

Often textbook solutions to induction problems like this are magically "pulled out of a hat" - completely devoid of intuition. Below I explain the intuition behind the induction in this proof. Namely, I show that the proof easily reduces to the completely trivial induction that $\rm\ 1^n\ \equiv\ 1\:$.

Since $\rm\ 15^n + 6 = 15^n-1 + 7\:,\: $ it suffices to show that $\rm\ 7\ |\ 15^n - 1\:.\: $ The base case $\rm\ n=1\ $ is clear. The inductive step, slightly abstracted, is simply the following

$\quad\quad\quad\quad\quad\rm\ \ \ \ 7\ |\ \ c\ -1,\ \ \ d\ \:-\ 1\ \ \Rightarrow\ \ 7\ |\ cd-1 = (c-1)\ d + (d-1)$

$\quad$ thus $\quad\ \ \ 7\ |\ 15-1,\ 15^n-1\ \ \Rightarrow\ \ 7\ |\ 15^{n+1}-1$

Said $\rm\ mod\ 7,\ \ 15\equiv 1\ \Rightarrow\ 15^n\equiv 1^n\equiv 1\ $ by inductively multiplying ("powering") using this:

LEMMA $\rm\ \ A\equiv a,\ B\equiv b\ \Rightarrow\ AB\equiv ab\ \ (mod\ m)\quad\quad$ (product rule for congruences)

Proof $\rm\ \ m\: |\: A-a,\:\:\ B-b\ \Rightarrow\ m\ |\ (A-a)\ B + a\ (B-b)\ =\ AB - ab $

Notice how this transformation from divisibility form to congruence arithmetic form has served to reduce the induction to the triviality $\rm\: 1^n \equiv 1$. Many induction problems can similarly be reduced to trivial inductions by appropriate conceptual preprocessing. Always think before calculating!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.