# Proof by induction that $3^n - 1$ is an even number

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

• Remember that $\text{even}\times\text{odd}=\text{even}$ and that $\text{even}+\text{even}=\text{even}$. – Akiva Weinberger Jun 9 '15 at 21:36
• 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})$$ – user26486 Jun 9 '15 at 21:53

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

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

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

• ...except that is not induction. – Joffan Jun 9 '15 at 20:58
• 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. – Brian Tung Jun 9 '15 at 21:08
• @BrianTung The problem is so simple that any random observation could be worked into induction; nevertheless the answer above does not do that. – Joffan Jun 9 '15 at 21:38
• 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. – Brian Tung Jun 9 '15 at 22:08

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

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

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

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.

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}

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.

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