2
$\begingroup$

Prove that $ \phi(n) =11 \cdot 3^n + 3 \cdot 7^n - 6 $ is divisible by 8 for all $n \in N$.

Base: $ n = 0 $

$ 8 | 11 + 3 - 6 $ is obvious.

Now let $\phi(n)$ be true we now prove that is also true for $ \phi(n+1)$.

So we get $ 11 \cdot 3^{n+1} + 3 \cdot 7^{n+1} - 6$ and I am stuck here, just can't find the way to rewrite this expression so that I can use inductive hypothesis or to get that one part of this sum is divisible by 8 and just prove by one more induction that the other part is divisible by 8.

For instance, in the last problem I had to prove that some expression a + b + c is divisible by 9. In inductive step b was divisible by 9 only thing I had to do is show that a + c is divisible by 9 and I did that with another induction, and I don't see if I can do the same thin here.

|cite|improve this question
$\endgroup$
4
$\begingroup$

Suppose $11*3^n + 3*7^n - 6 = 8k$

The $11*3^{n+1} + 3*7^{n+1} - 6 = 11*3^n*3 + 3*7^n*7 - 6$

$=3(11*3^n + 3*7^n-2) + 4*3*7^n $

$= 3(11*3^n + 3*7^n - 6) + 4*3*7^n + 12$

$= 3(8k) + 4(3*7^n + 3)$; $3*7^n$ is odd and $3$ is odd so $(3*7^n + 3)$ is even.

$= 3(8k) + 8(\frac{3*7^n + 3}2) = 8(3k + \frac{3*7^n + 3}2)$.

======

Actually I like and am inspired by Bill Dubuques answer.

We want to prove $\phi(n) = 11*3^n + 3*7^n - 6 \equiv 0 \mod 8$

And we know $\phi(n) = 11*3^n + 3*7^n - 6 \equiv 3*3^n + 3*(-1)^n -6 = 3^{n+1} + 3*(-1)^n - 6 \mod 8$.

So it's a matter of showing $f(n) = 3^{n+1} + 3(-1)^n \equiv 6 \mod 8$.

And if we notice $f(n+2) = 3^{n+3} + 3(-1)^{n+2} = 3^{n+1}*9 + 3(-1)^{n} \equiv 3^n + 3(-1)^{n}= f(n) \mod 8$.

So it's now just a matter of showing for $f(0) \equiv f(1) \equiv 6 \mod 8$.

Which is easily verified $3^1 + 3*(-1)^0 =3+3= 6$ and $3^2 + 3*(-1)^1 = 9 -3 = 6$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Yap, that's it. Thank you, just what I was looking for. $\endgroup$ – stigma6 Jan 27 '17 at 7:15
  • $\begingroup$ You want a secret confession? When I began answering I didn't know how it would turn out. But I know I had to factor $f(n+1) = manipulate(f(n)) = manipulate(8k)$ and I had faith that $manipulate(8k) = 8j$ and I just chewed on it to see what would happen. That's how a lot of figuring induction proofs. You know $f(n) = Property(t)$ and $f(n+1) = manipulate(f(n))=manipulate(Property(t))$ and know you want $manipulate(Property(t))=Property(s)$. Then you just gum and chew away until you get it. $\endgroup$ – fleablood Jan 27 '17 at 7:36
2
$\begingroup$

${\rm mod}\ 8\!:\ f(n\!+\!2)\equiv f(n)\,$ by $\,a\equiv 3,7\,\Rightarrow\,a^{\large 2}\equiv 1\,\Rightarrow\,a^{\large n+2}\equiv a^{\large n}.\,$ Thus $\,8\mid f(n)\iff 8\mid f(n\!+\!2),\,$ hence by (strong/parity) induction, it is true for all $n$ $\iff$ it is true for the base cases $\,n=0,1.$

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ @Downvoter The downvote is puzzling. If something is not clear then please feel welcome to ask questions and I will be happy to elaborate. This is one of the easiest ways to prove it, $\endgroup$ – Bill Dubuque Jan 26 '17 at 22:40
  • $\begingroup$ If congruences are unknown then we can eliminate them, viz. show that $8$ divides $\,f(n\!+\!2)-f(n)\,$ because $8$ divides $\,3^{\large n+2}-3^{\large n} = (3^{\large 2}-1)3^{\large n} = 8\cdot 3^n,\,$ and similarly $8$ divides $\,7^{\large n+2}-7^{\large n}.\ \ $ $\endgroup$ – Bill Dubuque Jan 26 '17 at 23:04
1
$\begingroup$

Setup the same as your current work:

$\dots$

$\dots = 11\cdot 3^{n+1}+3\cdot 7^{n+1}-6 = 11\cdot 3\cdot 3^{n}+ 3\cdot 7\cdot 7^n - 6$

$=33\cdot 3^n + 21\cdot 7^n - 6 = (11+22)\cdot 3^n + (3 + 18)\cdot 7^n - 6$

$=\underbrace{11\cdot 3^n + 3\cdot 7^n - 6}_{\text{should be familiar}} + \underbrace{22\cdot 3^n + 18\cdot 7^n}_{\text{unknown}}$

Now, what can we say about $22\cdot 3^n+18\cdot 7^n$? Anything? You say in a previous example, you had to run a second induction proof to finish, might that be useful here?

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ fyi: your answer was downvoted 1 second before mine, so it doesn't appear that the downvoter took the time to carefully consider the answers. $\endgroup$ – Bill Dubuque Jan 26 '17 at 22:50

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.