Mathematical Induction for $4 + 10 + 16 +…+ (6n−2) = n(3n +1)$

Question

Use mathematical induction to prove:

$$4 + 10 + 16 +…+ (6n−2) = n(3n +1)$$

I'm having a hard time understanding the induction process. Can someone please explain this to me?

Answer 1

Since you are asking about the inductive process in general, let's use a classic example. Suppose I asked you to sum the numbers from $1$ to $100$ and then someone standing next to you immediately said "$5050$". If you didn't know there was a simple formula to do this you may be impressed. If I told you the formula was $$s=\frac{n(n+1)}{2}$$ where $s$ is the sum, how would you verify that the formula worked?

You would try it for different numbers. You would start with $1$, then $2$ then maybe you would try $10$ or $20$ and others until you were confident that the formula worked.

But how would you prove that it works for every number? You cannot try an infinite set of numbers because you don't have an infinite amount of time. This is where induction comes in.

The idea is this. I can establish that the formula works for a single number. That is what we call the base case. We usually use $0$ or $1$. That's usually pretty easy. Now, for the ingenious part. We can't try every number so we say, suppose it is true for some number. We call that $k$. We then prove that if the formula works for $k$, it must work for $k+1$. That's the trick. We assume nothing about $k$ except that it is a number. By proving that if the formula works for $k$ it works for $k+1$ we establish that whenever we've demonstrated the truth of the formula for say $10$, it must be true for $11$.

Now we use that result with our base case of $1$. Since the formula works for $1$, it works for $2$. Since it works for $2$ it must work for $3$ and so on. In that way we have proved that the formula is true for all numbers.

Let's do it for this formula. The sum of all numbers from $1$ to $1$ is $1$ and $\frac{1(1+1)}{2}=\frac{2}{2}=1$ so the formula works for $n=1$. That's the base case.

For the inductive part, we assume the formula is true for $k$. That means we are assuming that $1+2+...+k=\frac{k(k+1)}{2}$.

Therefore, $1+2+...+k+(k+1)= \frac{k(k+1)}{2}+k+1=\frac{k(k+1)}{2}+\frac{2(k+1)}{2}=\frac{(k+1)(k+2)}{2}$

and $$\frac{(k+1)(k+2)}{2}= \frac{(k+1)((k+1)+1)}{2}$$ which if you look at carefully you will see is exactly what we would have gotten by plugging $k+1$ into our formula.

Therefore, we conclude that the formula works for all numbers.

Answer 2

Consider the very first time you were ever told that there is no largest number. You were probably told: "Take any number. Now add one to it. That number is bigger. Now add one to that. No matter what number you think of you can always add one to it. So there is no biggest number."

That's induction in a nutshell.

If you can show something is true for the number 1. And then you can show that for any number that the something is true for, then that something has to be true for the next number. Well, then it has to be true for the number after that. And the number after that. And the number after that. Ad infinitim. Thus it must be true for all numbers.

So to do a prove by induction you must do two things

1) Initial step: Show something is true for n = 1

2) Induction step: Show that for cases where something is true for n, then it must also be true for n+1.

And that's it. You showed it was true for 1, Then you should that if it's true for n, it must be true for n+1. THEREFORE It is true for 2. Therefore it is true for 3, therefore it is true for 4, therefore it is true for.....

So Claim: n is not the largest positive integer for any positive integer.

Proof:

Initial step: 1 is not the largest positive integer because 2 > 1.

Induction step: Assume it's true that n is not the largest integer. Then n + 1 exists and is larger. But n + 1 < n + 2. So n+1 is not the largest integer.

End of Proof.

(because 1 is not the largest. Therefore 1+1 = 2 is not the largest. And so on.

=====

So 4 + 10 + 15 + ... + (6n-2) = n(3n+1)

Initial Step: n =1: 6n-2 =4; n(3n + 1) = 4. So it's true for 4.

That was sleek. Let's show for n = 2 just to be safe: n = 2; 4 + 10 = 14 = 2(3*2 + 1). It checks.

Induction step: We assume 4 + 10 + 16 + ....+(6n - 2) = n(3n + 1).

We want to show it is true for n+1.

4 + 10 + 16 +....+ (6n - 2) + (6(n+1) - 2) = ????

4 + 10 + 16 +....+ (6n - 2) + (6(n+1) - 2) =

[4 + 10 + 16 +....+ (6n - 2)] + (6(n+1) - 2)=

n(3n + 1) + (6(n+1) - 2)= (because we assumed it was true for n)

3n^2 + n + 6n + 6 - 2 = 3n^2 + 7n + 4 = (n+1)(3n + 4) = (n+1)(3(n+1) + 1)

Which is what we wanted to show.

So it's true for n=1. If it's true for 1 then it is true for 1+1= 2. Therefore it is true for 2 + 1=3. Therefore it is true for 3+ 1=4, etc.

Answer 3

You first check that the case holds for n=1. when n=1, LHS = 4 and RHS = 4, so the equation holds.

Now we want to extend this result by proving that if the equation holds for n=k, then it would hold for n=k+1. So think about this, I didn't specify what k is, so it could be any integer. so I take n=1 is true and I can deduce that n=2 is true. I take n=2 is true and I can decude n=3 is true. You keep going and you'll find that there is no positive integers that you cannot cover in this way. This is how they use induction to prove an equation works for all positive integers.

So being more specific in your case, you assume the equation holds for n=k.

i.e. $4 + 10 + 16 +…+ (6k−2) = k(3k +1) ------(a)$

then for $n=k+1, $

$LHS = 4 + 10 + ... + (6k-2) + 6(k+1)-2 = k(3k+1) + 6(k+1)-2 = 3k^2+7k+4 $

$RHS = (k+1)(3(k+1)+1) = (k+1)(3k+4) = 3k^2 + 7k +4 = LHS$

so the equation is true for $n=k+1$ if we assume it is true for $n=k.$

using the logic above, we can extend the equation to all positive integers

Answer 4

There is a formal proof that induction works but it is easier to just use your intuition. The first step is to check if the statement is true for a starting value. Nothing hard so far. Next we prove that if the statement is true for k then it is true for k+1. What this says, if you have a value for which the statement is true, then the next value after it is also true. Since we checked at the beginning that the statement is true for a starting value, then from what we just showed it is true for the next value. using the same logic is is true for the next value too, an so on.

Let's use your exercise as an example. We check if the statement is true for $n=1$.

$(6*1-2)=1(3*1+1)$
$4=4$
So the statement is true for $n=1$.
Now the next step is to assume that the statement is true for n=k
$4 + 10 + 16 +…+ (6k−2) = k(3k +1)$
Now using this asusmption we have to prove that the statement is true for n=k+1. To prove that we have to simply add the term $(6(k+1)-2)$ to both sides of the assumption, since we know it is true.
$4 + 10 + 16 +…+ (6k−2)+(6(k+1)-2) = k(3k +1)+(6(k+1)-2)$
Let's look at the right side now
$k(3k +1)+(6(k+1)-2)=3k^2+k+6k-4=(k+1)(3(k+1)+1)$

Since this is the form we wanted to acquire we have proven the statement is true for all Natural numbers.