Benjamin Pasternak
HW3:

1. sum(2k-1) = n^2
a. induction :
    Base case: for n = 1 we have 2*1 -1 = 1^2. They are the same so passes
    inductive step: show that
    1 + 3 + ... + (2k-1) + (2k+1) = (k+1)^2
    proof:
    1 + 3 + ... + (2k-1) + (2k+1) = k^2 (2k+1)
    rhs = (k+1)^2
    lhs = 1 + 3 + ... + (2k-1) + (2k+1)
    Thus we have proved that statement is true by inducton
b. Geometrical proof:
    * * * * * gamma 5 = 9
    * * * * * gamma 4 = 7
    * * * * * gamma 3 = 5
    * * * * * gamma 2 = 3
    * * * * * gamma 1 = 1
    each gamma maps to an odd number so therefore it is proof its a square number thing

c. Dr.Z's method
    fact1:
    if P(n) is a polynomial of degree k then
    S(n) = p(1)+p(2)+...+p(n) = sum(p(i), i=1...n)
    is automatically a polynomial of degree k+1
    fact 2: if Two polynomials of degree k coincide in k+1 different
    places they are always the same

    so to prove sum(2k-1,i=1..n)=n^2,
    n=1: 2*1-1 = 1^2 -> 1 = 1
    n=2: 2*1-1 + 2*2-1 = 2^2 -> 4 = 4
    n=3: 2*1-1 + 2*2-1 + 2*3-1 = 3^2 -> 9 = 9
    n=4: 2*1-1 + 2*2-1 + 2*3-1 + 2*4-1= 4^2 -> 16 = 16
    Thus by fact 1: we know that

2. prove sum(k, i=1..n)=n(n+1)/2

a. induction:
    base case: for n=1: 1 = 1(1+1)/2 -> 1 = 1 True
    Inductive step: if n=k show that
    1 + 2 + ... + k + k+1 = (n+1)(n+2)/2
    proof:
    1 + 2 + ... + k = k(k+1)/2
    1 + 2 + ... + k + k+1 = k(k+1)/2 + k+1
    rhs = (k+1)((k+1)/2) = (k+1)((k+2)/2) = (k+1)(k+2)/2 Thus we have inductive step
    and problem is proved for n = k

b.
   * gamma 1 = 1
  * * gamma 2 = 2
 * * * gamma 3 = 3
 where T(n) is a sum t(1) = 1, t(2) = 2 ...
 t(n) where gamma = n gives above output
 This was demonstrated in class and is proved here geometrically

c. Dr.Z method:
fact1:
    if P(n) is a polynomial of degree k then
    S(n) = p(1)+p(2)+...+p(n) = sum(p(i), i=1...n)
    is automatically a polynomial of degree k+1
    fact 2: if Two polynomials of degree k coincide in k+1 different
    places they are always the same

    so to prove sum(2k-1,i=1..n)=n^2,
    n=1: 1 = 1(1+1)/2 -> 1 =1
    n=2: 1 + 2 = 2(2+1)/2 -> 3 = 3
    n=3: 1 + 2 + 3 = 3(3+1)/2 -> 6 = 6
    n=4: 1 + 2 + 3 + 4 = 4(4+1)/2 -> 10 = 10
    Thus by fact 1: we know that for a polynomial of degree k, the sum of 1..n
    of its components should be a polynomial of degree k+1
    and thus if 2 polynomials of degree k coincide in k+1 places they are always the same
    thus proved

3. Derive formula for sum(k^2, i=1..n)
since the sum of linear sum(k, i=1..n) -> n(n+1)/2  as above we know that it is a
quadratic. Thus we should want a cubic for our desired formula. This is true because of rule
one in Dr.Z's method.

so we know that it will be a cubic a^3-b^3 = (a-b)(a^2+ab+b^2)
so then lets start with n^3-(n-1)^3=(n-n+1)(n^2+n(n-1)+(n-1)^2)
= (n^2+n^2-n+n^2+1-2n) = 3n^2-3n+1

then let us examine (n-1)^3 - (n-2)^3=
3(n-1)^2-3(n-1)+1
same pattern holds for (n-2)^3 - (n-3)^3 ...

so if we add all of these patterns together
we get n^3 = 3*sum(n^2)-3*sum(n) + n

n^3 = 3*sum(n^2)-3(n(n+1)/2) + n

SO: sum(n^2) = 1/3(n^3+(3n(n+1)/2)-n)
= n/3(n^2+(3(n+1)/2)-1)
= n/3((2n^2+3n+3-2)/2)
= n/6((2n^2+3n+1))
= n/6((2n^2+2n+n+1))
= n/6(2n+1)(n+1) FIN (This was ridiculously hard)

the dr.Z method i assume would be to say that since from fact 1
we know that the function describing this should be of degree 3 this should be a
valid function

a. induction:
Base case: if n=1: 1 = 1 true
Inductinve step: let 1 + 2 + 4 + ... + n^2 = n/6(2n+1)(n+1)
show for n+1
proof turn lhs into rhs when n+1:
1^2 + 2^2 + ... + n^2 + (n + 1)^2 = (1^2 + 2^2 + ... + n^2) + (n + 1)^2
= n(n + 1)(2n + 1)/6 + (n + 1)^2
= (n + 1)(n( 2n + 1) + 6(n + 1))/6
= (n + 1)(2n^2 + 7n + 6)/6
= (n + 1)(n + 2)(2n + 3)/6

b. Dr.Z method:
    fact1:
    if P(n) is a polynomial of degree k then
    S(n) = p(1)+p(2)+...+p(n) = sum(p(i), i=1...n)
    is automatically a polynomial of degree k+1
    fact 2:
    if Two polynomials of degree k coincide in k+1 different
    places they are always the same

    so to prove sum(n^2,i=1..n)=,
    n=1: 1 = 1/6(2+1)(1+1) -> 1 = 1
    n=2: 1 + 4 = 2/6(2*2+1)(2+1) -> 5 = 5
    n=3: 1 + 4 + 9 = 3/6(2*3+1)(3+1) -> 14 = 14
    n=4: 1 + 4 + 9 + 16 = 4/6(2*4+1)(4+1) -> 30 = 30
    Thus by fact 1: we know that for a polynomial of degree k, the sum of 1..n
    of its components should be a polynomial of degree k+1
    and thus if 2 polynomials of degree k coincide in k+1 places they are always the same
    thus proved

4. prove sum(k^3) = (n(n+1)/2)^2
    fact1:
    if P(n) is a polynomial of degree k then
    S(n) = p(1)+p(2)+...+p(n) = sum(p(i), i=1...n)
    is automatically a polynomial of degree k+1
    fact 2:
    if Two polynomials of degree k coincide in k+1 different
    places they are always the same

    so to prove sum(n^2,i=1..n)=,
    n=1: 1 = (1(1+1)/2)^2 -> 1 = 1
    n=2: 1 + 8 = (2(2+1)/2)^2 -> 9 = 9
    n=3: 1 + 8 + 27 = (3(3+1)/2)^2 -> 36 = 36
    n=4: 1 + 8 + 27 + 64 = (4(4+1)/2)^2 -> 100 = 100
    Thus by fact 1: we know that for a polynomial of degree k, the sum of 1..n
    of its components should be a polynomial of degree k+1
    and thus if 2 polynomials of degree k coincide in k+1 places they are always the same
    thus proved