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.

Comments

topicTopics
academics study skills MCAT medical school admissions SAT expository writing college admissions English MD/PhD admissions GRE GMAT LSAT strategy writing chemistry math physics ACT biology language learning test anxiety graduate admissions law school admissions interview prep MBA admissions homework help AP exams creative writing MD personal statements academic advice career advice study schedules summer activities Common Application history premed philosophy test prep computer science secondary applications organic chemistry supplements economics PSAT admissions coaching grammar ESL law statistics & probability psychology SSAT covid-19 legal studies reading comprehension 1L CARS logic games USMLE dental admissions Spanish calculus engineering mathematics parents research Latin verbal reasoning DAT excel political science French Linguistics Tutoring Approaches academic integrity chinese DO MBA coursework Social Advocacy biochemistry case coaching classics diversity statement genetics geometry kinematics medical school mental health quantitative reasoning skills time management AMCAS Anki IB exams ISEE MD/PhD programs PhD admissions admissions advice algebra art history artificial intelligence astrophysics athletics business business skills careers data science internships letters of recommendation mentorship science social sciences software engineering tech industry trigonometry work and activities 2L 3L Academic Interest DMD EMT English literature FlexMed Fourier Series Greek Italian MD vs PhD MMI Montessori Pythagorean Theorem Python STEM Sentence Correction Step 2 TMDSAS Zoom algorithms amino acids analysis essay architecture argumentative writing campus visits cantonese capacitors capital markets cell biology central limit theorem chemical engineering chess chromatography class participation climate change clinical experience cold emails community service constitutional law cover letters curriculum dental school distance learning enrichment european history executive function finance first generation student fun facts functions gap year harmonics health policy history of medicine history of science hybrid vehicles induction information sessions institutional actions integrated reasoning intern international students investing investment banking lab reports logic mandarin chinese mba mechanical engineering medical physics meiosis mitosis music music theory neurology office hours operating systems pedagogy phrase structure rules plagiarism poetry pre-dental presentations proofs pseudocode quantum mechanics resonance resume school selection simple linear regression sociology software stem cells study abroad synthesis teaching technical interviews transfer typology units virtual interviews writing circles