Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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/… –  Derek Jennings Feb 16 '11 at 12:41
    
@Derek Jennings: Like this? –  Templar Feb 16 '11 at 12:55
1  
@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}.$ –  Derek Jennings Feb 16 '11 at 18:45
    
@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. –  Pete L. Clark Feb 16 '11 at 22:59
    
(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...) –  Pete L. Clark Feb 16 '11 at 23:00

3 Answers 3

up vote 16 down vote accepted

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

share|improve this answer

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

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

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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