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.

$\endgroup$

4 Answers 4

Reset to default
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$

$\endgroup$
2
  • $\begingroup$ Yap, that's it. Thank you, just what I was looking for. $\endgroup$
    – stigma6
    Jan 27, 2017 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, 2017 at 7:36
3
$\begingroup$

$\!\!\bmod 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}.\,$ So $\,8\mid f(n)\!\!\iff\!\! 8\mid f(n\!+\!2)$ thus by (strong/parity) induction, it is true for all $n$ $\iff$ it is true for the base cases $\,n=0,1.$

$\endgroup$
1
  • $\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, 2017 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?

$\endgroup$
3
  • $\begingroup$ And what can we say about $22 \cdot 3^n + 18 \cdot 7^n$? I don't see any connection to prove divisible by $8$? $\endgroup$
    – Andrej
    Jul 21, 2020 at 19:31
  • $\begingroup$ @Andrej This is an old post... It appears my intention was to help the OP complete the proof with the work they had already started with rather than completely trashing their attempt and starting fresh. My hint, if I understand what I wrote correctly, was that one could do a completely separate proof of why $22\cdot 3^n + 18\cdot 7^n$ should be divisible by $8$, possibly by induction again. $\endgroup$
    – JMoravitz
    Jul 21, 2020 at 19:50
  • $\begingroup$ As for a quick sketch of a proof, $22\cdot 3^n + 18\cdot 7^n = 2\cdot (11\cdot 3^n + 9\cdot 7^n)$ so it suffices to show that $11\cdot 3^n + 9\cdot 7^n$ is divisible by $4$. Noting that $7 = 3+4$ we can see this is $11\cdot 3^n + 4\cdot (\text{stuff})+9\cdot 3^n = 20\cdot 3^n + 4\cdot \text{stuff}$ is indeed divisible by $4$, completing the proof where here $\text{stuff}$ is what was left over by expanding $7^n=(3+4)^n = 3^n+n\cdot 3^{n-1}\cdot 4 + \binom{n}{2}\cdot 3^{n-2}\cdot 4^2 + \dots$ via the binomial theorem $\endgroup$
    – JMoravitz
    Jul 21, 2020 at 19:53
0
$\begingroup$

Write $\phi(n) =11 \cdot 3^n + 3 \cdot 7^n - 6\cdot 1^n$. This is an integer linear combination of geometric sequences and so satisfies an integer linear recurrence. Indeed, $$ \phi(n+3) = 11 \phi(n+2) - 31 \phi(n+1) + 21 \phi(n) $$ The claim now follows from induction once you have proved the base cases for $n=0,1,2$.

The recurrence comes from the equation having $3$, $7$, and $1$ as roots: $$0=(x-3)(x-7)(x-1)=x^3 - 11 x^2 + 31 x - 21$$ If $u$ is root of that equation, then $u^{n+3} = 11 u^{n+2} - 31 u^{n+1} + 21 u^n$ for all $n$. For the argument above, the coefficients are irrelevant, except for the fact that they are integers.

$\endgroup$
2
  • $\begingroup$ See also math.stackexchange.com/a/3525180/589 $\endgroup$
    – lhf
    Apr 13, 2020 at 13:43
  • $\begingroup$ Why do such induction exercises exist? To me they give the impression to the students that they need flashes of genius to manipulate the expressions into a form that gives the claim. This misses the opportunity to teach some real math and use induction in a meaningful way. $\endgroup$
    – lhf
    Apr 13, 2020 at 13:43

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.