The magic of induction

academics induction mathematics

What is the sum of the first n positive integers? Phrased mathematically: 1 + 2 + 3 … + n -1 + n = ?. The answer, it turns out, is n * (n + 1) / 2. How do we show this is true though? How do we prove this?

One way is to dive head first into the sum and manipulate it so that we arrive at the answer. What can we do with: 1 + 2 +… + n -1 + n ? We can pair opposite sides of this sum and add those! 

1 - - - n = n + 1

2 - - - (n - 1) = n + 1

3 - - - (n – 2) = n + 1

.

.

.

n/2 - - - (n/2 + 1) = n + 1

Note, these all add to n + 1. And there are n/2 pairs! That gives us a total of n/2 * (n+1) = n(n+1)/2 !

At this point, some readers might be thinking: “Wait… what if n is odd? Then we won’t be able to pair all the numbers up.” Good point. If n is odd, we’ll have the middle number left over. But, the middle number will be (n + 1)/2. And, there will only be (n – 1)/2 pairs. So, the total remains the same.

(End Proof)

Whew, that was a little tedious and took some ingenuity.

Notice, with the above technique, we actually derived the answer. But, we were given the answer to start with! Is there a way to show a formula is true without deriving it? Cue, induction!

Induction

Induction is a technique for proving that a formula is true for all positive integers. It asks us to show that a formula has a particular property: if the formula is true for some number (call it k), it is also true for the next number, (k + 1). After this, all we need to do is show that the formula is true for k = 1. What follows is magic. Because the formula is true for k = 1, it is also true for k+1 = 2. Then, because it's true for 2, it's true for 3, and so on. Induction.

Let's try this out on our formula for the sum of the first n positive integers.

Step 1: Show that if the formula is true for some number k, it’s also true for the next number, k+1.

 

Imagine that for some number k, 1 + 2 + 3 … + k-1 + k = k(k + 1)/2. Imagine that this is true. Given this, does 1 + 2 … + k-1 + k + k+1 = (k + 1)(k + 2)/2 ? That is, is the formula true for k+1? 

What can we do with 1 + 2 … + k-1 + k + k+1 ? We can substitute in the formula for the sum of the first k numbers! So, 1 + 2 … + k-1 + k + k+1 = k(k + 1)/2 + k+1 = k(k + 1)/2 + 2(k + 1)/2 = (k+2)(k+1)/2. 

Done!

Step 2: Show that the formula is true for k = 1.

 

This’ll be short and sweet. What is the sum of the first 1 number? 1. Does this = 1 * (1 + 1)/2 = 1 * (2)/2 = 1. Yes.

To conclude, because the formula is true for k = 1, it’s true for k + 1 = 2. And because it’s true for 2, it’s true for 3, and so on.

(End proof)

Wow, I don’t know about you, but that felt like no work compared to the first proof. That’s what I call magic.

In conclusion

Induction is even more powerful when applied to more complicated formulas like the sum of the first n cubes, which require sophisticated techniques to derive.

I learned induction in high school and used it mechanically for years before I fully understood and appreciated it. Now, I honestly feel like it’s one of the most awesome things I’ve ever learned. I hope I conveyed some of my excitement for induction to you in this article. Keep proving.

Madhav graduated with a degree in Computer Science with Honors from Caltech. After graduating, he worked at Oracle as a software engineer; more recently, he joined BallerTV, a fast growing sports-streaming startup, as a full-stack engineer.

Comments

topicTopics
academics study skills MCAT medical school admissions SAT college admissions expository writing English strategy MD/PhD admissions writing LSAT GMAT physics GRE chemistry biology math graduate admissions academic advice law school admissions ACT interview prep test anxiety language learning career advice premed MBA admissions personal statements homework help AP exams creative writing MD test prep study schedules computer science Common Application mathematics summer activities history philosophy secondary applications organic chemistry economics supplements research grammar 1L PSAT admissions coaching law psychology statistics & probability dental admissions legal studies ESL CARS PhD admissions SSAT covid-19 logic games reading comprehension calculus engineering USMLE mentorship Spanish parents Latin biochemistry case coaching verbal reasoning AMCAS DAT English literature STEM admissions advice excel medical school political science skills French Linguistics MBA coursework Tutoring Approaches academic integrity astrophysics chinese gap year genetics letters of recommendation mechanical engineering Anki DO Social Advocacy algebra art history artificial intelligence business careers cell biology classics data science dental school diversity statement geometry kinematics linear algebra mental health presentations quantitative reasoning study abroad tech industry technical interviews time management work and activities 2L DMD IB exams ISEE MD/PhD programs Sentence Correction adjusting to college algorithms amino acids analysis essay athletics business skills cold emails finance first generation student functions graphing information sessions international students internships logic networking poetry proofs resume revising science social sciences software engineering trigonometry units writer's block 3L AAMC Academic Interest EMT FlexMed Fourier Series Greek Health Professional Shortage Area Italian JD/MBA admissions Lagrange multipliers London MD vs PhD MMI Montessori National Health Service Corps Pythagorean Theorem Python Shakespeare Step 2 TMDSAS Taylor Series Truss Analysis Zoom acids and bases active learning architecture argumentative writing art art and design schools art portfolios bacteriology bibliographies biomedicine brain teaser campus visits cantonese capacitors capital markets central limit theorem centrifugal force chemical engineering chess chromatography class participation climate change clinical experience community service constitutional law consulting cover letters curriculum dementia demonstrated interest dimensional analysis distance learning econometrics electric engineering electricity and magnetism escape velocity evolution executive function fellowships freewriting genomics harmonics health policy history of medicine history of science hybrid vehicles hydrophobic effect ideal gas law immunology induction infinite institutional actions integrated reasoning intermolecular forces intern investing investment banking lab reports letter of continued interest linear maps mandarin chinese matrices mba medical physics meiosis microeconomics mitosis mnemonics music music theory nervous system