3
$\begingroup$

Use mathematical induction to prove that 6(n+2) + 7(2n+1) is divisible by 43 for n >= 1.

So start with n = 1:

6(1+2) + 7(2(1)+1) = 63 + 73 = 559 -> 559/43 = 13. So n=1 is divisible

Let P(k): 6(k+2)+7(2k+1) , where k>=1

Show that P(k+1): 6((k+1)+2) + 7(2(k+1)+1) is true

= 6(k+1+2) + 7(2k+2+1) = 6(k+3) + 7(2k+3)

I'm unsure where to go from here, I've tried several directions after this but have got nowhere. I don't know how to get the 43 or 559 out the front.

Any help would be great

$\endgroup$
1
$\begingroup$

$$6^{k+3} + 7^{2k+3} = 6\times6^{k+2} + 49\times7^{2k+1} = 6\times(6^{k+2} + 7^{2k+1}) + 43\times7^{2k+1}$$

$\endgroup$
  • $\begingroup$ That's a quick way to get 43 but there is still no common factor between the two? $\endgroup$ – puddles25 May 14 '14 at 13:28
  • $\begingroup$ Note that LHS is P(k+1) and RHS is $6\times P(k) + 43\times7^{2k+1}$. What do you know about P(k)? $\endgroup$ – TenaliRaman May 14 '14 at 13:30
  • $\begingroup$ its equal to 43*m where m >= 13? $\endgroup$ – puddles25 May 14 '14 at 13:42
  • $\begingroup$ Yes, that is the induction hypothesis step. But choose some other alphabet other than n, since it is already being used to represent the power. Say P(k) = 43*m, where m >= 13. Substitute that and you will get the common factor of 43. $\endgroup$ – TenaliRaman May 14 '14 at 13:46
  • 1
    $\begingroup$ As I show in my answer, above is a special case of the proof of the Congruence Product Rule, viz. $\begin{eqnarray} \\ \color{#0a0}{A\equiv a}, &&\ \color{#c00}{B}&\color{#c00}\equiv& \color{#c00}b &\,\Rightarrow\,& AB\ -\ ab &=\,& a(\color{#c00}{B\ -\ b}) &+& (\color{#0a0}{A-\,a})B &=\,& 0\\ \color{#0a0}{7^2\equiv 6}, && \color{#c00}{7^{2k+1}}&\equiv& \color{#c00}{-6^{k+2}} &\,\Rightarrow\,& 7^{2k+3}\!+6^{k+3}\! &=\,& 6(\color{#c00}{7^{2k+1}\!+6^{k+2}})\! &+& (\color{#0a0}{7^2\!-6})7^{2k+1} &\equiv\,& 0_{\phantom{I_I}} \\ \end{eqnarray}$ $\tag*{}$ RHS of prior = RHS of the above answer. $\endgroup$ – Bill Dubuque May 14 '14 at 15:37
2
$\begingroup$

Hint $\ $ Note $\ 43 = 6\cdot 7 + 1 = 6^2+6+1\ $ and apply

Lemma $\ \ a^2\!+a+1\mid a^{n+2}+(a+1)^{2n+1}\! =: b$

Proof $\, \ {\rm mod}\,\ a^2\!+a+1\!:\ \color{#0a0}{a(a+1)\equiv -1}$ and $\,\color{#c00}{a^3\equiv 1}\ $ by $\,0\equiv (a\!-\!1)(a^2\!+a+1) = a^3\!-1,\,$ so

$\qquad\quad\! a^{2n+1}b = a^{3n+3} + (\color{#0c0}{a(a+1)})^{2n+1} \equiv\, (\color{#c00}{a^3})^{n+1}\!-1\equiv 0\ $ so $\ b\equiv 0\ \ $ QED

Remark $\ $ If desired you can convert the above to an explicit inductive proof since the proof boils down to $\color{#0a0}{(-1)^{2n+1}\equiv -1}\,$ and $\color{#c00}{1^{n+1}\equiv 1},\,$both of which have obvious inductive proofs (a special case of the Congruence Power Rule inductive proof, see my other answer here).

$\endgroup$
  • $\begingroup$ $\color{#0a0}{(-1)^{2n+1}\equiv -1}$ and maybe point to your second answer for the explicit inductive proof? $\endgroup$ – Anant May 14 '14 at 17:56
1
$\begingroup$

writing it as $36(6^n) + 7(49^n)$ and then reducing mod 43 might yield some fruit.

$\endgroup$
1
$\begingroup$

Below I expain the innate arithmetical structure at the heart of such inductive proofs. This viewpoint allows us to quickly and easily reduce the proof to the trivial induction that $\, 1^n\equiv 1.\,$

Here is the inductive step $\,P(k)\,\Rightarrow\,P(k\!+\!1)\,$ written in intuitive congruence arithmetical form

$$\begin{eqnarray} {\rm mod}\ 43\!:\quad\ \ \color{#c00}{7^{\large 2}} &\equiv& \color{#c00}6\\ \color{#0a0}{7^{\large 2k+1}}&\equiv& \color{#0a0}{-6^{\large k+2}},\quad\ {\rm i.e.}\ \ \ P(k)\\ \Rightarrow\ \ 7^{\large 2(k+1)+1} &\equiv& \color{#c00}{7^{\large 2}}\: \color{#0a0}{7^{\large 2k+1}}\\ &\equiv& \color{#c00}6 (\color{#0a0}{- 6^{\large k+2}})\\ &\equiv& {-}6^{\large k+3},\quad {\rm i.e.}\ \ \ P(k+1) \end{eqnarray}\qquad$$

by the Congruence Product Rule $\ A\equiv a,\ B\equiv b\,\Rightarrow\, AB\equiv ab.\, $ If congruence arithmetic is unfamiliar it can be eliminated by unwinding the proof of the Product Rule, yielding

$\quad \begin{eqnarray} 0\,\equiv\, \color{#c00}{A}&\color{#c00}-&\color{#c00}a, &&\ \color{#0a0}{B}&\color{#0a0}-& \color{#0a0}b &\Rightarrow& \qquad AB\ -\ ab &=& a\ \ (\color{#0a0}{\ B\ \ -\ \ b}\ ) &+& (\color{#c00}{A-a})B\,\equiv\, 0\\ 43\,\mid\, \color{#c00}{7^2}&\color{#c00}-&\color{#c00}6, && \color{#0a0}{7^{2k+1}}\!&\color{#0a0}+&\! \color{#0a0}{6^{k+2}} &\Rightarrow& 43\mid 7^{2k+3}\!+6^{k+3}\! &=& 6(\color{#0a0}{7^{2k+1}\!+6^{k+2}}) &+& (\color{#c00}{7^2\!-6})7^{2k+1}\phantom{I^{I^I}} \\ \end{eqnarray}$

The prior is precisely the standard inductive proof that is usually pulled out of hat, like magic, without any intuitive motivation. We can employ further congruence arithmetic to make it even more obvious than above. Note $\,P(k)\,$ is $\,7\cdot 49^k\equiv -36\cdot 6^k\equiv 7\cdot 6^k\ $ so $\,P(k\!+\!1)$ arises simply by multiplying by $\,49\equiv 6\ $ to get $\, P(k\!+\!1)\!:\ 7\cdot 49^{k+1}\equiv 7\cdot 6^{k+1}.\, $ Even more clearly, by dividing, we see that $\,P(k)\,$ is equivalent to $\,(49/6)^k\equiv 1.\,$ But $\,49\equiv 6\,$ so $\,49/6\equiv 1,\,$ so the induction boils down to the trivial induction that $\,1^k\equiv 1,\,$ which is a simple special case of the inductive proof of the Congruence Power Rule.

Similarly, many inductions can be transformed into such standard or trivial inductions. Hence it is well-worth the effort to spend some time looking for such innate structure. This is especially true for divisibility problems, since transforming to congruence form allow us to exploit our well-honed arithmetical intuition, which is much stronger than our intuition on divisibility relation caculus.

$\endgroup$
0
$\begingroup$

The sequence $A_n = 6^{n+2} + 7^{2n+1}$ satisfies a two term linear recurrence relation with integer coefficients. Specifically it satisfies $A_n = 55A_{n-1} - 294A_{n-2}$ but we don't actually care what the relation is. If $43$ divides $A_n$ for two consecutive $n$ then by induction it must divide every term after that. So it is enough to check this for say $n = 0$ and $n=1$.

$\endgroup$

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.