# Proof by induction | Sequences, series and induction | Precalculus | Khan Academy

Share
Embed
• Published on Aug 9, 2011
• Proving an expression for the sum of all positive integers up to and including n by induction
Watch the next lesson: www.khanacademy.org/math/precalculus/seq_induction/proof_by_induction/v/alternate-proof-to-induction-for-integer-sum?YT&Desc&Precalculus
Missed the previous lesson?
www.khanacademy.org/math/precalculus/prob_comb/prob_combinatorics_precalc/v/birthday-probability-problem?YT&Desc&Precalculus
Precalculus on Khan Academy: You may think that precalculus is simply the course you take before calculus. You would be right, of course, but that definition doesn't mean anything unless you have some knowledge of what calculus is. Let's keep it simple, shall we? Calculus is a conceptual framework which provides systematic techniques for solving problems. These problems are appropriately applicable to analytic geometry and algebra. Therefore....precalculus gives you the background for the mathematical concepts, problems, issues and techniques that appear in calculus, including trigonometry, functions, complex numbers, vectors, matrices, and others. There you have it ladies and gentlemen....an introduction to precalculus!
About Khan Academy: Khan Academy offers practice exercises, instructional videos, and a personalized learning dashboard that empower learners to study at their own pace in and outside of the classroom. We tackle math, science, computer programming, history, art history, economics, and more. Our math missions guide learners from kindergarten to calculus using state-of-the-art, adaptive technology that identifies strengths and learning gaps. We've also partnered with institutions like NASA, The Museum of Modern Art, The California Academy of Sciences, and MIT to offer specialized content.
For free. For everyone. Forever. #YouCanLearnAnything
Subscribe to Khan Academy’s Precalculus channel:
thexvid.com/channel/UCBeHztHRWuVvnlwm20u2hNA
Subscribe to Khan Academy: thexvid.com/user/khanacademy

## Comments • 360

• Brian Dube 5 days ago

Amazing! Sal you're the best!

• ItsUr Mom 9 days ago

Pleass donate for khanacademy

• SetTheCurve 16 days ago

He needed to spend a lot more time on that final step because I have no idea what the connection was with the original equation.

• Cary Dominic Abejuro 24 days ago

I'm now a 2nd Year Secondary Education Student Major in Mathematics and it is only by now that I've understood this topic well....

• KingUnity 27 days ago

That reveal at the end blew my mind. I didnt even realize that he had exactly rewritten the original formula.

• dakota gagne Month ago

Very helpful. Made way more sense than my lectures

• Ulitarism Month ago +2

proof by seduction 😏

• Yeahhh!)

• OhnoItsFranc 3 months ago

Got my test tomorrow ayyy

• Elijah Sokoni 3 months ago

WOW!!! This is definitely something else. The examples are always easier than the task. We're having a test today and this is killing me.

• cee em 5 months ago

i keep seeing ppl make examples with s(k) before s(k+1) , then i see s(k-1) before s(k) , im so confused! does this work either way? can somene please give me a final answer?

• JasonJason210 5 months ago

It's not clear to me what the goal is with algebra after you add (k +1) at 5:42. I can see the logic of it, and how it result at 7:20 proves the proposition, but each proposition is different. I feel I need some general guidance when it comes to re-writing after the 5:42 stage. What are we after, generally?

• maimed lord 6 months ago

long live Khan Academy!

• Ahmed hisham 7 months ago

Man everytime I'm struggling to understand something i always know that you will have a great explaintion to it thank you so much!

• md abdool 7 months ago

This video in 2019 makes me wonder how people watched these videos without 1.5x and 2x speed

• Amber Little 8 months ago

you rock Sal

• Rajat Chhabra 8 months ago +2

You did not mention why we should use 'proof by induction' in the first place? In which situations can we use this?

• [Insert Name] 10 months ago

I don't know how they do it.
I go into a video confused as shit,
5 minutes in it clicks
after the video i know it like the back of my hand.
Love it!

• The Cold Tomato 10 months ago

i remember doing this as a high school freshman and i died

• gabi lovesinging 11 months ago

Omg thk u sm ! ! ! Best explanation evrrrrrrrrrr

• Kevin Ha 11 months ago +1

How about induction divisibility?

• Anonymous 11 months ago +2

OMG YOU SOMEHOW MADE IT CLICK FOR ME YOU ABSOLUTE LEGEND

• john holme Year ago

Thanks for taking the time to produce these videos. You have a talent for teaching mathematics and physics for the layman. Thanks to these videos I now have a good intuitive understanding of numerous mathematical and physics concepts. Keep up the good work.

• Nsovo Ntshuxeko Year ago

Just checked In Now..18thOct2018..Limpopian

• SHEROHE Year ago

Butter then MIT free courses.

• Patrik Lindfors Year ago +1

This guy is so clear in everything he says. Most teachers would skip most of the stuff he's explaining because they feel it's obvious. Khan never assumes that anything is obvious and that is why his videos are so easy to follow.

• Marius VanDamme Year ago

"true for two, true for three, true for four". Now THATS a tongue twister.

• Tau Chen Yeh Year ago

LIFESAVER!!!!!!!!!!

• Eugene Park Year ago

Dude. This video is about 7 years old but IT IS GOLD!!!! Thank you so much!!

• Ian Mark Year ago

i love you so much❤❤❤

• This genuinely makes me happy.

• Abdullah A Year ago +1

I understand..... nothing

• Ernest Ng Year ago

man, you have no idea how many lives you saved

• Victor Serra Year ago +2

What i don't get about Mathematical Induction is why do you just *assume* something is true for *n* and then show it's true for *n+1* , when what you wanted to do in the first place is *prove* that thing is true for *n*

• Joshua McNair Year ago

the reason is, if you can prove that it works for the base case n, which in this example is 1... and you can prove it for n+1, you can also prove it for any n, +1. You want to prove that it's true for every n, not only the first n.

• MuffinsAPlenty Year ago

Just restating what pcakes already said but in a different way:
When you assume it is true for n, and prove from that assumption that the statement is true for n+1, what you're doing is proving the conditional statement: "If it is true for some natural number n, then it is also true for n+1"
This statement, taken together with the base case, allows you to recursively work your way up to any positive integer.
Let's say your base case is n=1.
Since you know it's true for n=1, and since you know that if it is true for some natural number, it must be true for that natural number +1, you get that it must be true for 1+1 = 2.
Since you know it's true for n=2, and since you know that if it is true for some natural number, it must be true for that natural number +1, you get that it must be true for 2+1 = 3.
Since you know it's true for n=3, and since you know that if it is true for some natural number, it must be true for that natural number +1, you get that it must be true for 3+1 = 4.
etc.
The induction step is powerful! But, at the end of the day, it's a _conditional_ statement. It's useless without the "condition" being verified, so it doesn't work without the base case.

• pcakes Year ago +3

Victor Serra When he says "if we assume it's true for k, then we know it's true for k+1", all he means is that we know that something is true, so long as the previous one is true. He also shows that it's true for k = 1, so then we can conclude that k = 2 is true as well, since it comes right after. At that point, we can see that it's also true for 3, then 4, and so on.

• Lixon Darvish Year ago

Just made my day

• Lixon Darvish Year ago

Woooow

• Nick Kapiskis Year ago

Thank you so much, everything is so clear now!

• Lil Scotchy Year ago

So, after confirming the base case, what you want to do is show that S(k) + (k+1) = S(k+1)?

• Andrew Jager Year ago

Is it just me or are the font colours (British spelling) super juicy

• Brian A Year ago +4

why can we just assume it works for all of k?

• SHALTILL 3 months ago

If it works for a k then it also works for k +1 [Proven];
It works for one [Proven];
Then it works for two;
Then it works for three;
Then it works for four;
...

• JUAN 12345 5 months ago

Thats the part I dont get. I could prove anything assuming anything.

• poop Year ago

Can someone please correct me if i'm wrong with my understanding:
By proving something with induction is to first assume n=k and then by proving n=k+1 to be true.
E.g. Killing a cow will get you beef, killing a thousand cows will still get you beef.

• Unterseeboots Year ago

you're averting suicides here buddy.

• Moneera Saleh Year ago

Excuse me, are you Tom Hanks?

• Mike Weiss Year ago

Awesome explanation. Really cleared this up for me. Also, I'd like you to know that when I do math, I repeat things in my head like you do during these lectures as I write them out lol, with different "pronunciations" as I repeat them. Thanks for that.

• Awais Naveed Year ago

thank you so much, I was really stuck, but one thing clicked and now I understand. thank you

• Shenella Marks Year ago

Honestly, n=1 and n=k are simple. n=k+1 however, is a bit confusing...

• Mariokart360 Year ago

I love you. Have my children

• Good4Y0u Year ago

Why is there no audio?

• A bit hard to read but clear expanation

• Toby Hang Year ago

The check mark on point.

• Drex Beckman Year ago

It finally clicked. Thank you, Sal.

• Cha Eun-Woo Year ago

Why do we have to add the (k+1) in to the left side of the equation? Also do have to add that (k+1) in to the left side of the equation whenever we want to prove induction?

• Gelila N Year ago

you are a life saver

• Zeveria Year ago +9

"Assume true for K", this part pisses me off. No. You don't get to assume. I may as well say "assume 2+2= 1" and just leave it at that. This truly sounds like a bunch of nonsense.

• Eoin Higgins 10 months ago

@MuffinsAPlenty Thank you very much. Cleared up my problems with prooving by induction 🙌

• MuffinsAPlenty Year ago +18

Yes, you make an assumption, and that assumption may _not_ be true! This is why the base case is necessary!
When you assume it is true for k, and prove from that assumption that the statement is true for k+1, what you're doing is proving the conditional statement: "If it is true for some natural number k, then it is also true for k+1"
This statement, taken together with the base case, allows you to recursively work your way up to any positive integer.
Let's say your base case is k=1.
Since you know it's true for k=1, and since you know that if it is true for some natural number, it must be true for that natural number +1, you get that it must be true for 1+1 = 2.
Now, since you know it's true for k=2, and since you know that if it is true for some natural number, it must be true for that natural number +1, you get that it must be true for 2+1 = 3.
And since you know it's true for k=3, and since you know that if it is true for some natural number, it must be true for that natural number +1, you get that it must be true for 3+1 = 4.
etc.
The induction step is powerful! But, at the end of the day, it is a conditional statement. It's useless without the "condition" being verified. The base case verifies that "conditional" part of it.

• Babi Salazar Year ago

Facts

• Paul 123098 Year ago +2

so a+a=a-1 ? See that doesn't work for any number except -1 because you get a= -1 for all numbers lol

• Khokon Chowdhury 2 years ago

it was so much helpful. thanks a lot!!!

• Seatla Mongatane 2 years ago

Mind blown. Now to ace this section in my test

• Kylee Webb 2 years ago

Can there just be a choice to take online classes through Khan instead of going to Discrete Math class at college? I would take this professor over any other professor in a heart beat.

• KingSceptile 2 years ago

Minecraft

• MuffinMan 2 years ago

Dude I love your videos; but you repeat yourself so much, so often, and so fast in this one, I'm having to fight the compulsion to rage into a conniption fit. I can't tell if it is to help us remember concepts, or because of a compulsive habit, but I'm fucking twitching in my seat. Again, I fucking love your vids. You are a great teacher. You are there for me even when I have a professor that is completely unintelligible.

• MuffinMan 2 years ago

I upvoted it btw. Still the best introductory induction proof vid that is reasonably searchable. I don't want you to think I hate you

• Kyle Patrick 2 years ago

Lol I know this is cliche but this is a million times better than lectures