Teaching Kids Programming: Videos on Data Structures and Algorithms
Math Induction is a powerful tool that allows us to prove the correctness of a formula (Proposition). To do this, we need to follow two steps:
First, prove the formula is correct for the initial case (base case).
Second (and Last), assume the general case n, then prove that formula also stands for case n + 1.
Math Induction to Prove Sum of First N Natural Numbers
For example, we propose the formula to compute the sum of the first N natural numbers is (n+1)*n/2.
First Step: base case, when N = 1, the sum is obviously 1, so is the Proposition (1+1)*1/2.
Induction Step: Assume When N=K, thus the Sum is (K+1)*K/2. Then for K+1 cases, apparently the F(K+1)=F(K)+K+1 Thus
That is: 
as 
Therefore we can conclude that the Proposition n(n+1)/2 is the sum for the first N natural numbers.
Math Induction to Prove the Sum of Squares Formula
Proposition: Sum of 1^2 + 2^2 + 3^2 + … n^2 = 
Base case: when N is 1: the sum is 1*(1+1)*(2*1+1)/6 which is 1.
Induction Step: given K=N, then the sum for K+1 is 
Expanded:
Thus, F(K+1) is
we have proven the F(1), and also proved that F(K+1) based on assumption of F(K).
Thus the Proposition is correct.
Sum of First N Squares is
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Find the Length of the Collatz Sequence
Next Post: Simple Vertical Cipher Algorithm
