Teaching Kids Programming – Sum of First N Odd Numbers (with Math Induction)


Teaching Kids Programming: Videos on Data Structures and Algorithms

The Sum of First N Odd Numbers goes like this 1, 1+3=4, 1+3+5=9, 1+3+5+7=16 … As we can guess the sum of the first N Odd numbers is equal to N squared.

Sum of First N Odd Numbers using Loop

We can accumulate each odd numbers:

1
2
3
4
5
def sumOfOdd(N):
  ans = 0
  for i in range(1, 2*N, 2):
    ans += i
  return ans
def sumOfOdd(N):
  ans = 0
  for i in range(1, 2*N, 2):
    ans += i
  return ans

This takes O(N) time, and O(1) space.

Sum of First N Odd Numbers using Math Induction

Proposition: f(N) is the sum of the first N Odd Numbers and it is equal to N^2.

Base case: When N is 1, f(1) = 1 which is correct as the only odd number here is one.
Assume, N=K, f(N), and if we add one more odd number, which is 2*K+1, thus:

tex_179b6958e7af5f0c0d0cc733aeadb101 Teaching Kids Programming - Sum of First N Odd Numbers (with Math Induction) algorithms math python teaching kids programming youtube video
tex_6bc1fd551a78cc9a6aa0230e08c16f81 Teaching Kids Programming - Sum of First N Odd Numbers (with Math Induction) algorithms math python teaching kids programming youtube video
therefore tex_6100612ade31ef016dd633a32c08faa2 Teaching Kids Programming - Sum of First N Odd Numbers (with Math Induction) algorithms math python teaching kids programming youtube video
By using Math induction, we have proved the sum of first N Odd Numbers is N^2.

Implementation of such is trivial:

1
2
def sumOfOdd(N):
  return N * N
def sumOfOdd(N):
  return N * N

The time complexity is O(1) constant, and the space complexity is also O(1). How about Sum the Even Numebrs? Teaching Kids Programming – Sum of First N Even Numbers (with Mathematic Induction)

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
455 words
Last Post: Parentheses Grouping Algorithm
Next Post: Algorithm to Make a List Equal with Increments

The Permanent URL is: Teaching Kids Programming – Sum of First N Odd Numbers (with Math Induction)

Leave a Reply