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$
2
  • $\begingroup$ Remember that $\text{even}\times\text{odd}=\text{even}$ and that $\text{even}+\text{even}=\text{even}$. $\endgroup$ Jun 9, 2015 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, 2015 at 21:53

9 Answers 9

6
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ ...except that is not induction. $\endgroup$
    – Joffan
    Jun 9, 2015 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, 2015 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, 2015 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, 2015 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$

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

$\endgroup$
2
  • 1
    $\begingroup$ You should use another variable in the RHS. $\endgroup$
    – user65203
    Jun 9, 2015 at 21:47
  • $\begingroup$ Thank you, that was poor variable choice $\endgroup$
    – nosyarg
    Jun 9, 2015 at 21:48
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .