Prove by induction: $3^n+1$ is divisible by $2$ for $n\ge 0$

Question

I'm going through the process of induction and when I'm attempting to prove $P_{k+1}$ I keep getting $2(3A-\frac32)$, where $A$ is an integer and $A\geq 1$, which isn't possible since $3A-\frac32$ should be an integer.

My method is to write $P_k$ as $3^k+1=2A$, where $A$ is an integer and $A\geq 1$. Then for $P_{k+1}$ I write $3^{k+1}+1=2A$ and then I try to make the $LHS$ equal to the RHS.

Where am I going wrong?

Answer 1

For $k+1$, you already assume that $3^k + 1 = 2n$ for some integer $n$. Then, use the fact that

$$3^{k+1} + 1 = 3\cdot 3^{k} + 1$$

and substitute $3^k$ with the expression above.

Answer 2

You will never be able to make $3^{k+1}+1=3^k+1$

The idea behind induction is that you first prove that the statement holds for some $k$. Then you show that if it holds for $n$, it must hold for $n+1$ and hence for $n+2$ etc. (Note that the step might change from time to time)

In your case for $n=1$ we have $3^n+1=4$ which is even.

Suppose the statement holds for some $n$, i.e. $3^n+1$ is even.

Then for $n+1$ we have that $3^{n+1}+1=3(3^n+1)-2$.

By the induction hypothesis the first term is even. Trivially, $2$ is even.

Hence the claim holds for $n+1$. By induction, the statement holds $\forall n \in \mathbb{N}$

Answer 3

Assume $3^k + 1$ is divisable by $2$, then $$3^{k+1} + 1= 3\times 3^{k} +1 = 3 \times 3^k +3 -2 = 3\times \underbrace{\left(3^k+1 \right)}_{\text{divisible by 2}} -2$$ and when you take 2 away from something that is divisible by two, it's still divisible by two. QED.

Answer 4

Hint: Let $x_n=3^n+1$. Then $x_{n+1}-1=3(x_n-1)$ and so $x_{n+1}=3x_n-2$.

Answer 5

The other solutions are all good, but here is one more done slightly differently.

What we know:

1. Any odd number plus 1 is even

2. An odd number times an odd number is an odd number

So, $3^0=1$ is odd, and $3^0+1=2$ is even. Assume for some nonnegative integer $k$, we have $3^k$ is odd. Then $3^{k+1}=3\times 3^k$ is, by assumption, the product of two odd numbers, so it too is odd. Hence $3^n$ is odd for all $n\ge 0$ and $3^n+1$ is an odd number plus 1, so it is even.

Answer 6

To address where is the problem with the attempt described in the question.

My method is to write $P_k$ as $3^k+1=2A$, where $A$ is an integer and $A\geq 1$. Then for $P_{k+1}$ I write $3^{k+1}+1=2A$ and then I try to make the $LHS$ equal to the RHS.

The idea that you want to show that $3^{k+1}+1$ is twice some integer is correct. However, it will not be the same integer as for $3^k+1$.

So instead of \begin{align*} 3^k+1&=2A\\ 3^{k+1}+1&=2A \end{align*} you actually want \begin{align*} 3^k+1&=2A\\ 3^{k+1}+1&=2A' \end{align*}

As already explained in other answer, one way to go might be to express $3^{k+1}+1$ in some way using $3^k+1$. (There are many possibilities how to solve this, but if you are supposed to do this using induction, this seems like a natural one.)

Answer 7

If $2\mid3^k+1$, then $$ \begin{align} 3^{k+1}+1 &=3\cdot3^k+1\\ &=2\cdot3^k+\left(3^k+1\right) \end{align} $$ Since $2$ divides both $2\cdot3^k$ and $3^k+1$, we have $$ 2\mid3^{k+1}+1 $$