knuth - vol 1 - inductive proof questions

Hi,

I'm trying to solve yet another simple problem, but I think I am stuck
at one point.
I think I am lacking an idea how to formalize things.

The task is as follows:

Formulate and prove by induction a rule for the sums 1^2, 2^2 - 1^2,
3^2 - 2^2 + 1^2, 4^2 - 3^2 + 2^2 - 1^2, etc.

When I was first approaching this problem I noticed few things:

a_1 = 1
a_2 = 2^2 - 1^2 = 3
a_3 = 3^2 - 2^2 + 1^2 = 6
a_4 = 4^2 - 3^2 + 2^2 - 1^2 = 10
....
a_n = n^2 - a_{n-1}^2 or equivalently a_n = - a_{n-1} ^ 2 [1]

One of the other observations I made was for the formulation of a_n by
a_n = a_{n-1} + n [2]

Putting [1] and [2] on 2 sides of the equal sign yields

a_{n-1} + n = n^2 - a_{n-1}^2 [3]

After some algebra I get

2 * a_{n-1} = n^2 - n

and finally it is easy to get the formula for a_n, which is

a_n = [ (n+1) * n ] / 2 [4]


Before doing a proof by induction I am wondering if I am allowed to
use the formula [2] (which I have not derived by any means, and just
simply used the empirical observation) in equation [3] ?

I have tried deriving the formula [2] formally but kept failing
(probably making the same mistake all the time).
Can anyone possible please give me some hints on this one?


Assuming that formula [2] is valid, how do I proceed with proving [4]
for n+1 by induction?


Mateusz Berezecki


.

Relevant Pages

  • Re: knuth - vol 1 - inductive proof questions
    ... Mateusz Berezecki wrote in message ... I'm trying to solve yet another simple problem, but I think I am stuck ... I think I am lacking an idea how to formalize things. ... Before doing a proof by induction I am wondering if I am allowed to ...
    (sci.math)
  • Re: Response to Karen and to Willem on recursive proofs
    ... that the mathematician becomes a mathematical clerk. ... > I have never heard an empirical proof called 'inductive'. ... Mathematical "induction" was so named ... >) formalize something sufficiently and you have at least one computer, ...
    (comp.programming)
  • Re: knuth - vol 1 - inductive proof questions
    ... I think I am lacking an idea how to formalize things. ... Yeah, ... Some parts got lost during formatting process;-) ... For a proof by induction of the proposition ...
    (sci.math)