Fdtxjr

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?
beginalign
tagBasis 3^0-1&=0 \
tagBasis -3^1-1&=2 \
tagInduction step textFor $ngeq2$ qquad 3^n-1&=3cdot 3^n-1-1 \
&=3cdot(3^n-1-1)+2 \
&=3cdot 2k+2 quad textwhere $k inmathbbZ$ \
&=2cdot(3k+1) \
endalign

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

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.