If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Induction

# Proof of finite arithmetic series formula by induction

Proving an expression for the sum of all positive integers up to and including n by induction. Created by Sal Khan.

## Want to join the conversation?

• •  Mathematical induction is a method of mathematical proof typically used to establish a given statement for all natural numbers. It is done in two steps. The first step, known as the base case, is to prove the given statement for the first natural number. The second step, known as the inductive step, is to prove that the given statement for any one natural number implies the given statement for the next natural number. From these two steps, mathematical induction is the rule from which we infer that the given statement is established for all natural numbers.
• How does someone come up with a formula like this? How do I derive it?

Is this something obtained simply through observation that if you take a number and multiply it by the integer of adding one to it, and dividing by two that you obtain the sum of the integers up to and including itself; trial and error?

And is this process of trial and error common as you continue to progress towards more advanced theories like this one?

Thank you. •  Not a general method, but I came up with this formula by thinking geometrically. Summing integers up to n is called "triangulation". This is because you can think of the sum as the number of dots in a stack where n dots are on the bottom, n-1 are in the next row, n-2 are in the next row, and so on. The result is a triangle:
.
. .
. . .
. . . .
So we need a general formula for the number of dots in this triangle if we know the size of the base. 1/2*base*height doesn't quite work because of the jagged edge on the right, but the big insight is that you can copy the triangle, flip it upside down, then fit the two together to get an n*(n+1) rectangle. So the original triangle has half the dots of this rectangle, or n*(n+1)/2.
• I greatly appreciate these videos. But I'm not sure that I'm really getting the hang of it, though. Would it be possible to include a few exercises, giving us the opportunity to practice this a bit? • How would you prove 1+3+5+...+(2n-1)=n^2 by induction? • You would solve for k=1 first. So on the left side use only the (2n-1) part and substitute 1 for n. On the right side, plug in 1. They should both equal 1. Then assume that k is part of the sequence. And replace the n with k. Then solve for k+1.
k+1: 1+3+5+...+(2k-1)+(2k+1)=k^2+2k+1
The right hand side simplifies to (k+1)^2
• This is a very different kind of maths compared to calculus, in my opinion much more abstract because I like to SEE what something means. The process of mathematical induction confuses me quite a bit because I cannot seem to reason with myself as to how to go about getting to the solution. Why do we use the character "k" and not stick with "n", would the answer not be the same, and furthermore, would a better name for this process not simply be "substitution"? • me and my dad tried this sum of mathematical induction for over 1hr but were still unsuccessful. Could anyone help me in this?

1^2 + 2^2 + 3^2 +..............+ n^2= 1/6 * n(n+1)(2n+1) • Show it is true for a base case
∑ a^2 from a=1 to 1 = 1/6 * 1 * (1+1) * (2*1+1)
1^2 = 1/6 * 1 * 2 * 3
1 = 1 √ (that's a check)

Show that if it is true for k it is also true for k+1
∑ a^2, a=1...k+1 = 1/6 * (k+1) * (k+1+1) * (2t(k+1)+1)
(1^2 + 2^2 + 3^2 + ... + k^2) + (k+1)^2 = (This is the key step)
(k)(k+1)(2k+1)/6 + (k+1)^2 =
(k+1) * [(k)(2k+1)/6 + (k+1)] =
(k+1)/6 * [(k)(2k+1) + 6(k+1)] =
(k+1)/6 * (2k^2+k+6k+6) =
(k+1)/6 * (2k^2+7k+6) =
(k+1)/6 * (2k+3)(k+2) = (k+1)(k+2)(2k+3)/6 √

Hooray!
Where I said "this is the key step" was the key step (obviously). With these sum induction problems, it is typically best to group the first k addends and replace them with your assumed form. From there, it's just algebra.
• how would you solve 2+4+6+8+....2n=n(n+1) by induction? • First step base case , n=1: 2=1*(1+1), seems like works. Next let's assume that n is equal to some k (step 2): 2+4+...+2*k=k*(k+1). Now time to proof for n=k+1 elements, if it works for n=k elements and for (k+1) then it works for the whole series (), ok lets put (k+1):
2+4+..+2*k +2*(k+1)=(k+1)*((k+1)+1), BUT we assumed earlier that 2+4+..+2*k=k*(k+1), so we put to cut our series to:
k*(k+1)+2*(k+1)=(k+1)*((k+1)+1), now lets prove that left part is equal to right:(k+1)*(k+2)=(k+1)*((k+1)+1)
(k+1)*(k+1+1)=(k+1)*((k+1)+1)
(k+1)*((k+1)+1)=(k+1)*((k+1)+1), so now I can say that if we need to count sum of 2+4+6+8+..+2*n elements (n=10000 for example) this is the same thing as count it through equation n*(n+1), which is much faster and easier. •  