N^2 - (N-1)^2 + (N-2)^2 - (N-3)^2 + ... 1 =
1 + 2 + 3 + ... N
I am trying to prove the statement above by using induction however, I am not sure what the statement means
First I tried to find a base case when N=1
1^2 + 1 = 1 which is not true
Can someone please help me out? Thanks
Base case: the first is 1 when N=1, as is the second, hence the base case
holds.
Now suppose that for some k:
k^2 - (k-1)^2 + (k-2)^2 - (k-3)^2 + ... 1 = k + (k-1) + .. + 1
..............................................=k(k+1)/2
Now:
(k+1)^2 - k^2 + (k-1)^2 - ... 1
...........=(k+1)^2 - (k^2 - (k-1)^2 + (k-2)^2 - (k-3)^2 + ... 1)
...........=(k+1)^2 - (k + (k-1) + .. +1)
...........=(k+1)^2 - k(k+1)/2 = k^2/2 + 3k/2 + 1= (k+1)(k+2)/2
...........= (k+1) + k + .. +1.
So if the two expressions are equal for some N=k they are equal for N=k+1,
and they are equal for N=1, hence by induction they are equal for all
N>=1.
RonL
Thanks for all your help CaptainBlack. I would just like to make sure that I got the base case for the problem.
So the left side:
N^2 - (N-1)^2 + (N-2)^2 - (N-3)^2 + ... 1
Is equivalent to N(N+1)/2 so when N = 1, (base case) that would equal to 1(1+1)/2 =1
And for the right side:
1+2+3...N
It would be just 1 when N =1 right?
Not quite, we have
N^2 - (N-1)^2 + (N-2)^2 - (N-3)^2 + ... 1
and when N=1 is just 1, as there is but a single term.
The N(N+1)/2 is present in what I wrote as it is the sum of the first
N integers, that is:
1 + 2 + .. + N = N(N+1)/2,
the proof requires that the sum of the consecutive integers be replaced
by this short from to make the subsequent calculations simpler.
RonL