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

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

Brian Dube5 days agoAmazing! Sal you're the best!

ItsUr Mom9 days agoPleass donate for khanacademy

SetTheCurve16 days agoHe 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 Abejuro24 days agoI'm now a 2nd Year Secondary Education Student Major in Mathematics and it is only by now that I've understood this topic well....

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

dakota gagneMonth agoVery helpful. Made way more sense than my lectures

UlitarismMonth ago^{+2}proof by seduction 😏

Іван ПилипкоMonth agoYeahhh!)

OhnoItsFranc3 months agoGot my test tomorrow ayyy

Elijah Sokoni3 months agoWOW!!! 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 em5 months agoi 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?

JasonJason2105 months agoIt'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 lord6 months agolong live Khan Academy!

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

md abdool7 months agoThis video in 2019 makes me wonder how people watched these videos without 1.5x and 2x speed

Amber Little8 months agoyou rock Sal

Rajat Chhabra8 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 agoI 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 Tomato10 months agoi remember doing this as a high school freshman and i died

gabi lovesinging11 months agoOmg thk u sm ! ! ! Best explanation evrrrrrrrrrr

Kevin Ha11 months ago^{+1}How about induction divisibility?

Anonymous11 months ago^{+2}OMG YOU SOMEHOW MADE IT CLICK FOR ME YOU ABSOLUTE LEGEND

john holmeYear agoThanks 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 NtshuxekoYear agoJust checked In Now..18thOct2018..Limpopian

SHEROHEYear agoButter then MIT free courses.

Patrik LindforsYear 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 VanDammeYear ago"true for two, true for three, true for four". Now THATS a tongue twister.

Tau Chen YehYear agoLIFESAVER!!!!!!!!!!

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

Ian MarkYear agoi love you so much❤❤❤

Elena Karolína SemanováYear agoThis genuinely makes me happy.

Abdullah AYear ago^{+1}I understand..... nothing

Ernest NgYear agoman, you have no idea how many lives you saved

Victor SerraYear 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 McNairYear agothe 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.

MuffinsAPlentyYear agoJust 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.

pcakesYear 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 DarvishYear agoJust made my day

Lixon DarvishYear agoWoooow

Nick KapiskisYear agoThank you so much, everything is so clear now!

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

Andrew JagerYear agoIs it just me or are the font colours (British spelling) super juicy

Brian AYear ago^{+4}why can we just assume it works for all of k?

SHALTILL3 months agoIf 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 123455 months agoThats the part I dont get. I could prove anything assuming anything.

poopYear agoCan 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.

UnterseebootsYear agoyou're averting suicides here buddy.

Moneera SalehYear agoExcuse me, are you Tom Hanks?

Mike WeissYear agoAwesome 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 NaveedYear agothank you so much, I was really stuck, but one thing clicked and now I understand. thank you

Shenella MarksYear agoHonestly, n=1 and n=k are simple. n=k+1 however, is a bit confusing...

Mariokart360Year agoI love you. Have my children

Good4Y0uYear agoWhy is there no audio?

RB Maths and PhysicsYear agoA bit hard to read but clear expanation

Toby HangYear agoThe check mark on point.

Drex BeckmanYear agoIt finally clicked. Thank you, Sal.

Cha Eun-WooYear agoWhy 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 NYear agoyou are a life saver

ZeveriaYear 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 Higgins10 months ago@MuffinsAPlenty Thank you very much. Cleared up my problems with prooving by induction 🙌

MuffinsAPlentyYear 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 SalazarYear agoFacts

Paul 123098Year 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 Chowdhury2 years agoit was so much helpful. thanks a lot!!!

Seatla Mongatane2 years agoMind blown. Now to ace this section in my test

Kylee Webb2 years agoCan 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.

KingSceptile2 years agoMinecraft

MuffinMan2 years agoDude 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.

MuffinMan2 years agoI 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 Patrick2 years agoLol I know this is cliche but this is a million times better than lectures