I have a problem to understand k in the following induction proof.
Prove that $3^n -1$ is even for any natural number $n$.
Is there anybody that can show me that this is a valid proof and what is k in this case? \begin{align} \tag{Basis} 3^0-1&=0 \\ \tag{Basis} -3^1-1&=2 \\ \tag{Induction step} \text{For $n\geq2$} \qquad 3^n-1&=3\cdot 3^{n-1}-1 \\ &=3\cdot(3^{n-1}-1)+2 \\ &=3\cdot 2k+2 \quad \text{where $k \in\mathbb{Z}$} \\ &=2\cdot(3k+1) \\ \end{align}
On
It's is a valid proof but badly explained:
Claim: $3^n -1$ is even.
Case $n = 0$. $3^0 -1 = 0$ is an even number.
Case $n = 1$ we don't actually need to do this step but $3^1 -1 = 2$ and even number. (Presumably that negative sign is a typo.)
Induction Step: $n \ge 2$. AND we assume that we have already shown that $3^{n-1} -1$ is an even number. (As we have already done for $n =0$ and $n=1$). [The written proof never stated that we are making that assumption. If one is familiar with induction proofs it goes without saying, but for a novice it should be pointed out.]
Now for $n$:
$3^{n} -1 =$
$3*3^{n-1} - 1=$
$3(3^{n-1} -1) + 3 -1 =$
$3(3^{n-1} -1) + 2 =$
Now we assumed we have shown $3^{n-1} -1$ is an even number. Let's call that numbe $2k$ and substitute it in.
$= 3(2k) + 2 = $
$6k + 2 = $
$2(3k + 1)$. ANd that is in even number.
So if $n = 2$ and we know $3^1 -1$ is even we know $3^2 - 1$ is even. ANd if $n =3$ and we know $3^2 -1$ is even we know $3^3 -1$ is even. And if $n = 4$ and we know $3^3 -1$ is even we know $3^4 -1$ is even and so on forever.
The inductive step lets us go on forever.
....
That's the basic proof by induction.
1) Base Step: You show it for the first case.
2) Induction step: You show that if it is true of one case it will be true for that next.
Implication: You realize that if one case implies the next, and you have a first case, that means you have proven the second... and therefore the third.... and therefore the fourth .... and therefore every case.
====
FWIW
I'd do it this way.
Base case: $n = 0$
$3^0 -1 = 0$ and even number.
Induction step: Assume we know that $3^n -1 = 2k$ an even number. We will prove $3^{n+1} - 1$ is an even number:
$3^{n+1} - 1 =$
$3*3^{n} - 1 = $
$3(3^n -1) + 3 - 1=$
$3*2k + 3 - 1=$
$3*2k + 2 =$
$2(3k + 1)$ is an even number.
Implication: We have shown this is true for $n=0$. We have shown if in it true for $n$ it is true for $n +1$. So it is true for $n = 0+ 1= 1$; and for $n = 1+1=2$; and for $n=2+1=3$; and so on for all non-negative integers.
I may be mistaken, but it looks like this is a proof of the fact that numbers of the form $3^{n}-1$ for $n \in \mathbb{N}$ are even, meaning they can be expressed as $2k$ for integral $k$. The base cases, the second of which is both superfluous and and mistakenly has a negative in front of the $3^{1}$, show directly that this holds for $n = 0,1$. In the inductive step, it is proven that the claim holds for $n$, assuming that it holds for $n-1$. As you can see, the quantity $3^{n} - 1$ is - after a string of algebraic manipulations including the substitution $3^{n-1}-1=2k$ are performed - shown to be equal to twice an integer. In my mind, an easier proof would be to note that $3^{n}$ is always odd, and thus $3^{n} - 1$ is always even, but maybe this is more a demonstration of the technique of induction than of its result.