How to do a Proof by Induction

Question

I need to prove the following statement below by using induction. The problem is I have no clue what induction is and how I can approach it.

Thanks!

Prove by Induction:

$$3 + 7 + 11 + \cdots+ (4n-1) = 2n^2 + n \forall n \geq 1$$

Answer 1

try base case for n = 1 we can see 3 = ($2(1)^2 + 1) = 3$

now suppose formula is true for the case of n and we need to prove it holds for n + 1

$2(n + 1)^2 + n + 1$ = $2(n^2 + 2n + 1) + n + 1$ = $2n^2 + n + 2*(2n + 1) + 1$

Since formula is true for n we get $3 + 7 + 11 + .... + (4n - 1) + 4n + 3$ = $3 + 7 + 11 + ... + (8n + 2)$

which proves it since we needed to prove it holds for n + 1 that is

it must have this form $3 + 7 + 11 .... + (4n - 1) + (4(n + 1) - 1)$ = $3 + 7 + 11 + .... + 8n + 2$

Answer 2

If $$\sum_{r=1}^n(4r-1)=2n^2+n$$

$$\sum_{r=1}^{n+1}(4r-1)=\sum_{r=1}^n(4r-1)+\underbrace{4(n+1)-1}=2n^2+n+4n+3=2(n+1)^2+(n+1)$$

Answer 3

Induction is basically proving something for some $k_0$ then proving that if it holds for any $k$ then it must hold for $k+1$.

Thinking of it, if it holds for $k_0$, then it holds for $k_0+1$ but since it holds for $k_0+1$ then it holds for $k_0+2$, etc.

Now, for $n=1$,

$3=2(1)^2+1$

That is, the formula is true for $n=1$

Now, assume it holds for some arbitrary $n$, that is

$3+7+\ldots+(4n-1)=2n^2+n$

Then

$3+7+\ldots+(4n-1)+(4(n+1)-1)=2n^2+n+4(n+1)-1=2n^2+n+4n+4-1=2n^2+4n+2+n+1=2(n+1)^2+(n+1)$

That is, the formula holds for $n+1$ if it holds for $n$.

Thus, the formula is valid for all $n\in\mathbb{N}$

Answer 4

To perform a proof by induction, we evaluate the claim for the base case and see if it is true. The base case here is $n = 1$.

We see that since $4(1) - 1 = 3$ and $2(1)^{2} + 1 = 3$, then the base case holds for $n = 1$.

Now, the inductive step is to show that the claim's proof for some natural number $k$ implies the truth of the next natural number $k + 1$. So, we suppose that $3 + 7 + 11 + .. + (4k-1) = 2k^{2} + k$ and show, using that fact, that $3 + 7 + 11 + ... + (4k - 1) + 4(k + 1) - 1) = 2(k+1)^{2} + 1 $

These two demonstrations prove the theorem by the principle of mathematical induction. Here is why:

We know that the claim is true for $1$ by our first demonstration. We know that if the claim is true for $k$, then it is true for $k + 1$.

Thus, we have the following information:

The claim is true for $1$.

If the claim is true for $1$, then the claim is true for $2$.

If the claim is true for $2$, then the claim is true for $3$.

If the claim is true for $3$, then the claim is true for $4$.

If the claim is true for $4$, then the claim is true for $5$.

and so on, and so forth, forever.

The two statements "The claim is true for $1$" and "If the claim is true for $1$, then the claim is true for $2$." together means that the claim is true for $2$. This is called modus ponens.

Now, I have that the claim is true for $2$. Taking the statements "The claim is true for $2$" and "If the claim is true for $2$, then the claim is true for $3$" together means that the claim is true for $3$, just as above.

This "logical chain" continues indefinitely, and that's why induction works.