2
$\begingroup$

How to demonstrate that $3^n - 1$ is an even number using the principle of induction? I tried taking that $3^k - 1$ is an even number and as a thesis I must demonstrate that $3^{k+1} - 1$ is an even number, but I can't make a logical argument.

So I think it's wrong the assumption... Thanks

$\endgroup$
  • $\begingroup$ Remember that $\text{even}\times\text{odd}=\text{even}$ and that $\text{even}+\text{even}=\text{even}$. $\endgroup$ – Akiva Weinberger Jun 9 '15 at 21:36
  • $\begingroup$ More generally, $a-b\mid a^n-b^n$, because $$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\cdots +ab^{n-2}+b^{n-1})$$ $\endgroup$ – user26486 Jun 9 '15 at 21:53
2
$\begingroup$

Hint: try substituting back in $3^k = 2x+1$

$\endgroup$
  • 1
    $\begingroup$ You should use another variable in the RHS. $\endgroup$ – Yves Daoust Jun 9 '15 at 21:47
  • $\begingroup$ Thank you, that was poor variable choice $\endgroup$ – nosyarg Jun 9 '15 at 21:48
6
$\begingroup$

Hint: Start by showing that $3^n$ is odd. What's an odd minus an odd?

$\endgroup$
  • 1
    $\begingroup$ ...except that is not induction. $\endgroup$ – Joffan Jun 9 '15 at 20:58
  • 2
    $\begingroup$ How so? $3^0-1 = 0$ is even. For $n \geq 1, 3^{n-1}-1$ is even. Then $3^{n-1}$ is odd. Then $3^n$ is odd. Then $3^n-1$ is even. $\endgroup$ – Brian Tung Jun 9 '15 at 21:08
  • 1
    $\begingroup$ @BrianTung The problem is so simple that any random observation could be worked into induction; nevertheless the answer above does not do that. $\endgroup$ – Joffan Jun 9 '15 at 21:38
  • 1
    $\begingroup$ It doesn't, but I would guess that the OP understands how to work things into induction, and is mostly having difficulty framing the premise of the induction in a convenient form. This answer nudges the OP toward one such convenient form. $\endgroup$ – Brian Tung Jun 9 '15 at 22:08
3
$\begingroup$

Hint : $3^{k+1}-1=3(3^{k})-1=3(3^{k}-1)+3-1=3(3^{k}-1)+2$

$\endgroup$
2
$\begingroup$

First, $ 3^0 - 1 = 0 $ which is even so $3^n - 1 $ is even for $ n = 0 $

Suppose that $3^k - 1 $ is even. We need to show that $3^{k+1}- 1 $ is even. Well,

$ 3^{k+1}-1 = 3(3^{k}) -1 = 3(3^k - 1) + 2 $

By our assumption, $ 3^k-1 $ is even so $ 3^{k} - 1 = 2m $, for some integer $m$

Thus, $ 3(3^k - 1) + 2 = 3(2m) + 2 = 2(3m + 1) $ Note that, $3m + 1 \in Z $ since addition and multiplication are closed in $Z$. Thus, $2(3m + 1) = 3^{k+1} -1 $ is even which is want we need to show.

Therefore, $3^n -1$ is even for all $n > 0$.

$\endgroup$
1
$\begingroup$

Hint $\ $ Let $\,a = 2\,$ below (= first term of binomial expansion).

$\ \ \ \begin{align} (1+ a)^n\, \ \ =&\,\ \ 1 + ak\qquad\qquad\quad {\rm i.e.}\ \ P(n)\\[1pt] \Rightarrow\ (1+a)^{\color{#c00}{n+1}}\! =&\ (1+ak)(1 + a)\\[2pt] =&\,\ \ 1+ a\,(\underbrace{k\!+\!1\!+\!ka\!}_{\large k'})\ \ \ {\rm i.e.}\ \ P(\color{#c00}{n\!+\!1})\\ \end{align}$

Remark $\ $ If you know modular arithmetic (congruences) then you can view it as a special case of the Congruence Power Rule, i.e. $\, x\equiv 1\,\Rightarrow\, x^n\equiv 1^n\equiv 1\pmod{\!a},\,$ where the induction is conceptually clearer: $ $ the powering of a congruence, and the trivial induction $\,1^n\equiv 1.$

$\endgroup$
0
$\begingroup$

Let $3^k-1=2m$ for some $m\in\Bbb Z$.

$$3^{k+1}-1=3(3^k-1)+2=2(3m+1)$$

I definitely wouldn't use induction here though.

$\endgroup$
0
$\begingroup$

Note $3^1-1=2$ is even. Then:

$$\begin{align} \text{Given } &3^k-1 \text{ is even} \\ \implies 3(3^k-1) &= 3^{k+1}-3 \text{ is even} \\ \implies 3^{k+1}-3+2 &= 3^{k+1}-1\text{ is even} \\ &\square \end{align}$$

$\endgroup$
0
$\begingroup$

We assume that $3^k-1$ is even. This is the assumption of induction. We want to show that $3^{k+1}-1$ is even. We can rewrite this as $3 \cdot 3^k - 1$. Now calculate the difference between the two numbers:

$$(3\cdot 3^{k} - 1) - (3^k-1) = 3\cdot 3^k - 1 - 3^k + 1 = 3\cdot 3^k - 3^k$$ Now we can factor out $3^k$ so we get: $3^k(3-1)= 3^k2$, which is an even number. If you add an even number to an even number you always end up with an even number. Therefore the induction step is now complete.

$\endgroup$
0
$\begingroup$

$3^{k+1}$ and $3^k$ have the same parity as$$3^{k+1}-3^k=2\cdot3^k,$$

and so do $3^{k+1}-1$ and $3^k-1$.

The base case is $3^0-1=0$, even.

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