2

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.

user377892
  • 25

4 Answers4

4

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$

fleablood
  • 124,253
  • Yap, that's it. Thank you, just what I was looking for. – user377892 Jan 27 '17 at 07:15
  • 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. – fleablood Jan 27 '17 at 07:36
3

$\!\!\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.$

Bill Dubuque
  • 272,048
  • 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}.\ \ $ – Bill Dubuque Jan 26 '17 at 23:04
1

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?

JMoravitz
  • 79,518
  • 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$? – Andrej Jul 21 '20 at 19:31
  • @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. – JMoravitz Jul 21 '20 at 19:50
  • 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 – JMoravitz Jul 21 '20 at 19:53
0

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.

lhf
  • 216,483
  • See also https://math.stackexchange.com/a/3525180/589 – lhf Apr 13 '20 at 13:43
  • 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. – lhf Apr 13 '20 at 13:43