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.

I would like someone to check this inductive proof (sketch)

The base case is clear. For the inductive step, it follows that $8 \mid 9^{n+1} - 9 = 9(9^n - 1)$ by the indutive hyp. So $9^{n+1} \equiv 9 \equiv 1 \mod 8$.

Feedback would be appreciated.

share|improve this question
3  
Or note that since $9\equiv 1\pmod 8$, we have $ 9^n \equiv 1^n \pmod 8$. –  bonsoon Jan 30 '13 at 3:18

2 Answers 2

up vote 6 down vote accepted

I'm assuming you mean what you say when you state your work as a proof "sketch".

The base case is clear. For the inductive step, it follows that $8 \mid 9^{n+1} - 9 = 9(9^n - 1)$ by the indutive hyp. So $9^{n+1} \equiv 9 \equiv 1 \mod 8$.

In your final write up, I'd suggest you "fill in" a bit of detail: e.g., to "walk through" the base case, at least stating that the congruence holds for $n=1$, or perhaps

"for $n = 1$, clearly, $9\equiv 1 \pmod 8$".

Then I suggest you make your inductive hypothesis explicit:

"Assume that it is true that $9^n \equiv 1 \pmod 8$,"

and then finish with, "for the inductive step....[what you wrote]"


If your task was to prove the congruence holds using proof by induction on $n$, then you've done a fine job of sketching such a proof.

If you can use other strategies, then bonsoon's suggestion is worth considering:

"Or note that since $9 \equiv 1 \pmod 8$, we have $9^n\equiv 1^n = 1 \pmod 8.$"

share|improve this answer

Yes, that is correct. Alternatively, prove by induction the $\,\rm n$-ary congruence product rule

$$\rm\qquad\ \ a_k\equiv b_k\ \Rightarrow\ a_1\cdots\, a_n \equiv b_1\cdots\, b_n$$

by iterating the binary product rule $\rm\ a_k\equiv b_k\ \Rightarrow\ a_1 a_2 \equiv b_1 b_2,\:$ then specialize $\rm\:a_i \equiv 9,\ b_i\equiv 1$

Remark $\ $ Your proof can be viewed as special case of the obvious inductive proof that a sequence $\rm\:f_n\:$ is constant if successive values never change, i.e. if $\rm\:f_{n+1} \equiv f_n.$ Indeed, in your special case we have $\rm\:mod\ 8\!:\ f_{n+1} = 9^{n+1} = 9\, f_n \equiv f_n\:$ so the sequence is constant, hence $\rm\:f_n\equiv f_0\equiv 9^0\equiv 1.\:$

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.