Prove by induction: $3^n+1$ is divisible by $2$ for $n\ge 0$ 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?
 A: 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.
A: Hint: Let $x_n=3^n+1$. Then $x_{n+1}-1=3(x_n-1)$ and so $x_{n+1}=3x_n-2$.
A: 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
$$
A: 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}$
A: 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. 
A: The other solutions are all good, but here is one more done slightly differently.
What we know:


*

*Any odd number plus 1 is even

*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.
A: 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.)
