Suppose $n$ is a positive integer. Using induction, prove that there are unique integers $a\geq 0$ and $k>0$ such that $n=(3^a)\cdot k$ and $k$ is not divisible by $3$.

Note: I have already proven the base step of $P(1)$ and have set the induction hypothesis (I.H.) to be $P(t): t=(3^a)\cdot k$ [I used $t$ here instead of $k$ since $k$ already exists in the equation]. I am to the point of proving $P(t+1)$ but am unsure of whether or not this means $t+1=(3^a)\cdot k$ or if it means $t+1=(3^a)\cdot k+1$? With the latter, couldn't you just subtract a $1$ and then be left with your I.H.? If it is the first equation, I'm not quite sure how this can be proved. The induction proofs I have done so far were all summation problems, so I could group sections together and set it equal to the I.H. which doesn't seem to be a possibility here.

  • $\begingroup$ Are you sure the condition is $a \geq 0$ and not $a > 0$? With $a$ allowed to be $0$, the question doesn't even require an inductive proof, since $\forall t$ which are not divisible by 3, we have $t = (3^0) \cdot t$, and for those which are divisible by 3 you can use prime factorization to remove the 3s and then plug all the rest into $k$. Are you required to use induction here? $\endgroup$
    – MM8
    Jan 31 '17 at 1:09
  • $\begingroup$ I just re-checked the homework sheet, it is in fact $a\geq 0$. $\endgroup$
    – Deez1133
    Jan 31 '17 at 1:11
  • $\begingroup$ Like I said, the result then follows immediately from prime factorization. Why do you want to frame such a proof in an induction? It's not impossible but certainly kind of artificial to do so. $\endgroup$
    – MM8
    Jan 31 '17 at 1:21
  • $\begingroup$ In class today the professor just stated that he suggest we prove the statement by some form of induction. I guess he did not say it was required, but I was curious how this would be done. $\endgroup$
    – Deez1133
    Jan 31 '17 at 1:24
  • 1
    $\begingroup$ @TimonG. Results like this are usually proved before those much stronger results. $\endgroup$ Jan 31 '17 at 1:24

Hint $\ $ If $\,3\nmid n\,$ then $\, n = 3^{\large 0} n.\,$ Else $\,3\mid n\,$ so by induction $\,n/3\, =\, 3^{\large a}k,\ 3\nmid k,\,$ so $\,n = 3^{\large a+1}k.$

  • $\begingroup$ If we are assuming $P(n)$ to be true, wouldn't the resulting cases be $3\nmid n+1$ and $3\mid n+1$? $\endgroup$
    – Deez1133
    Jan 31 '17 at 1:38
  • $\begingroup$ @Deno1133 We used strong/complete induction, did you not yet learn that form of induction? Our induction hypothesis is that it is true for all $\,k< n,\,$ so, in particular, for $\,k = n/3.\ \ $ $\endgroup$ Jan 31 '17 at 1:40
  • $\begingroup$ Oh yes, I forgot there was both strong and weak induction. I'm fairly certain I understand now. Thank you so much for your help! $\endgroup$
    – Deez1133
    Jan 31 '17 at 2:10

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.