6
$\begingroup$

I am not sure how to go about this "proof by induction" problem. below is my attempt.

Base Case: $n = 0$,substituting the value of $n$ to the equation $3^n+1$ $$= 3^0 + 1$$ $$= 1 + 1 = 2 $$ Thus the equation holds true for initial value of $n$ i.e $0$

Induction Hypothesis: Suppose the equation holds true for all the values of $n$: $1,2,3....k$ therefore, $3^k + 1$ results even.

Induction Step: $n = k$ holds true,
to prove: $3^{k+1}+ 1$ for $n = k+1$

LHS: $$3^{k+1}+ 1 = (3^k \cdot 3) + 1 = (3^k \cdot (2 + 1)) + 1 = 2 \cdot 3^k + 3^k + 1$$

The above solution results even, because since multiplying any integer with $2$ gives even integer, and from the Induction Hypothesis $3^k+1$ is even.

Hence $3^{k+1} + 1$ is even, thus $3^{n+1}$ is even for all values of $n\ge0$

$\endgroup$
  • 13
    $\begingroup$ Looks good. I think it feels odd because the problem is so artificial...I mean, you use the fact that Even + Even= Even yet you are supposed to pretend you don't notice that Odd + Odd = Even. But, that said, I think your argument is good. $\endgroup$ – lulu Feb 17 '17 at 13:47
  • $\begingroup$ @lulu you should make that an answer so this question can be closed. $\endgroup$ – Stella Biderman Feb 17 '17 at 14:31
  • $\begingroup$ @Smit What happens if $n=\sqrt2$? $\endgroup$ – Michael Rozenberg Feb 17 '17 at 14:53
  • $\begingroup$ @user236182 Exactly my point. It's a very artificial problem. $\endgroup$ – lulu Feb 17 '17 at 14:54
  • 2
    $\begingroup$ @lulu It's not artificial, because (at this level), proving $3^n$ odd requires induction on $n,\,$ (e.g. using a product of odds is odd). $\endgroup$ – Bill Dubuque Feb 17 '17 at 18:27
1
$\begingroup$

Direct Proof:

$3^n$ has no factor of $2$, so it is odd. $3^n+1$ is one greater than an odd number.


Inductive Proof:

$3^0+1=2$ is even.

Suppose $3^n+1$ is even, then $$ 3^{n+1}+1=3\left(3^n+1\right)-2 $$ is an even number minus an even number, hence even.

$\endgroup$
  • $\begingroup$ may i know how u got 3 ( 3^n + 1) - 2? $\endgroup$ – Smit Feb 18 '17 at 3:17
  • 1
    $\begingroup$ @Smit: $3\left(3^n+1\right)-2=3^{n+1}+3-2=3^{n+1}+1$. $\endgroup$ – robjohn Feb 18 '17 at 10:00
1
$\begingroup$

Proof I

$$3^n + 1 \implies (2x + 1)+1 \implies 2x+2$$

Case: $n = 0$ $$ (2\cdot0 + 2) = 2 $$ Case: $n = n$ $$(2n + 2) = 2(n+1) $$ Case: $n = n+1$ $$(2(n+1) + 2) = 2n+4 = 2(n+2)$$ $$\Box$$


Proof II

$$(3^n + 1)\text{ mod }2 \implies (3^n + 2 -1) \text{ mod }2 \implies (3^n -1)\text{ mod }2 $$

Case: $n = 0$ $$3^0 \equiv 1 (\text{ mod }2)\implies 3^0 -1 \equiv 0 (\text{ mod }2)$$

Case: $n = n$ $$3^n \equiv 1 (\text{ mod }2)\implies 3^n -1 \equiv 0 (\text{ mod }2)$$ Case: $n = n+1$ $$3^{n+1} \equiv 1 (\text{ mod }2)\implies 3^{n+1} -1 \equiv 0 (\text{ mod }2)$$ $$\Box$$


Case of the Congruence Power Rule

$\endgroup$
0
$\begingroup$

An easier answer is to note that:

$3^n - 1 \equiv 1^n - 1 \equiv 0 (mod 2)$.Thus, we conclude that $2|(3^n -1)$. Hence, $3^n - 1$ is always 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.