Sunday, August 2, 2009

How much can you teach a computer?

How much math can you teach a computer? Consider finding an expression for the sum of the numbers from 1 to n.

I. Proof by induction: The computer should be able to do what students are asked to do, but this is not finding an expression, only verifying it.

2. Assume a quadratic form f(n) = an^2 + bn +c
A "little algebra" gives

f(n+1) - f(n) = 2an + (a+b)

the left-hand side of this equation, being the sum of the numbers from 1 to n+1 less the sum of the numbers from 1 to n is n+1. This gives us 2a =1 and a+b = 1 so a = 1/2 and b = 1/2. Our equation is now

f(n) = (n^2)/2 + n/2 + c

Setting n to 1 (or any number including 0) sets c to 0 giving our final equation

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

3. Manipulate the numbers using the distributive law. There are two cases depending on whether n is even (the simpler case) or odd. For the even case:

The sum of the numbers from 1 to n is equal to the sum of the numbers from 1 to n/2 plus the sum of the numbers from (n/2 plus 1) to n. The sum of the numbers from (n/2 plus 1) to n is the sum of the numbers from n to (n/2 plus 1). i.e. reverse order. Using summation pseudo-notation:
Sum(i=n/2 + 1 to n)(i) = Sum(i = 1 to i)(n+1-i)
Then
Sum(i=1 to n)(i) = Sum(i=1 to n/2)(i) + Sum(i=1 to n/2)(n+1-i)
=Sum(i=1 to n/2)(i+n+1-i) = Sum(i=1 to n/2)(n+1) = n/2 times n+1 . . . QED
The odd case is slightly more complicated or one could apply induction to the even case.

4. Graphical solution:

Take n vertical bars numbered 1 to n and set them side by side in ascending order. Each bar should be one unit wide and as many units high as its number. Draw a diagonal from the lower left corner to the upper right corner. The area under the diagonal is n squared over 2. Each of the n bars has half of a square unit extending above the diagonal making an area of n over 2. So n squared over 2 plus n over 2 is n(n+1)/2.
__________________________________________________
How much of this could the computer come up with. I'd like to see an AI expert teach it to learn math.
 

2 comments:

  1. I firmly doubt that computers will be able to do this at all, and still resemble a thing we would call a computer.

    ReplyDelete
  2. I was afraid of that but hope springs eternal. I have edited my post. Again

    ReplyDelete