Recurrence relation (Canadian Math Olympiad, 1970)?

Question

Let f(n) be the sum of n first terms of the following sequence:

0,1,1,2,2,3,3,4,4,5,5,...

Find a formula for f(n) and prove that

f(s+t)-f(s-t)=s*t for all s,t such that s>t>0.

Thanks.

Answer 1

If n is odd, n = 2m+1 then the sum  is simply twice the sum from 1 to m which is m(m+1) = (n-1)/2 ((n-1)/2+1) = (n-1)(n+1)/4 = (n²-1)/4 = n²/4 - 1/4.

If n is even, n=2m then the sum is simply twice the sum from 1 to m-1 plus the 2m-th term which is m for a total of m(m-1) + m = m² = 4n².

We then combine these two solutions (odd and even) by carefully using (-1)^n and we get the following:

f(n) = n²/4 - 1/8 + (-1)^n/8

Part 2

f(s+t) - f(s-t)

= (s+t)²/4 - 1/8 + (-1)^(s+t)/8 - (s-t)²/4 + 1/8 - (-1)^(s-t)/8

= (s+t)²/4 - (s-t)²/4 + (-1)^(s-t) [ (-1)^(2t) - 1 ]/8 ... taking common factor out

= (s+t)²/4 - (s-t)²/4 + (-1)^(s-t) [ 0 ] /8 ... 2t is even so (-1)^2t is always 1.

= (s²+2st+t²)/4 - (s²-2st+t²)/4

= 4st/4

= st

Answer 2

Note that the floor function is the easiest way to define this sequence:

for n=1,2,3,4,...

f(n) = floor(n/2) = 0,1,1,2,2,3,3,...

http://mathworld.wolfram.com/FloorFuncti...

But because it will not be true that

floor[ s/2 + t/2 ] - floor[ s/2 - t/2 ] = st

another way will have to be found.

Wow... I *REALLY* had to stare at this thing. I hate being old and dumb. Note that the expression 2n-1, which is the definition of an odd integer, I suppose, generates the following sequence:

1, 3,     5,     7,     9,    11,    13, ...

Now notice that if you subtract 1 from every odd term (i.e., the first term, third term, fifth term, and so on) you get the sequence:

0,3,4,7,8,11,12,15,16,...

Now if you add 1 to every even term you get

0,4,4,8,8,12,12,16,16, ...

The way to accomplish this is to add an alternating term to the expression 2n-1 to get

2n-1 + (-1)^n = 0     4     4     8     8    12    12    16    16    20    20

Here is the really neat part. Notice that every term in the sequence is divisible by 4, so now all you have to do is divide this sequence by  4 to get

f(n) = [ 2n-1 + (-1)^n ] /4 = 0,1,1,2,2,3,3,...

for n=1,2,3,...

OK ...

I do not know why I am unable to prove that f(s+t) - f(s-t) = st. It is entirely possoble that there could be another formula... still.

Note that:

f(s+t) = [ 2(s+t) - 1 + (-1)^(s+t) ]/4

f(s-t) = [ 2(s-t) - 1 + (-1)^(s-t) ]/4

But

f(s+t) - f(s-t) ≠ st

I don't know what to say. The formulas

f(n) = floor(n/2)

and

f(n) = [ 2n-1 + (-1)^n ] /4

both satisfy the sequence for n=1,2,3,... , yet neither satisfies the condition f(s+t)-f(s-t)=s*t. Oh well... hope I didn't make things worse for you...

Answer 3

Let f(n) = sum of a(i) over i = 1 to n, such that a(1) = 0, a(2) = 1, a(3) = 1, ...

First few f(n)'s are: 0, 1, 2, 4, 6, 9, 12.

It's obvious that a(n) is related to n/2, the explicit formula can be written for example using (-1)^2 (other possibilities include modulo or floor function).

a(n) = n/2 - 1/4 + (-1)^n/4.

A partial sum is

f(n) = n(n+1)/4 - n/4 + 1/4 * sum of (-1)^i over i = 1 to n

The sum in the tail is a sequence -1, 0, -1, 0, ..., or -(n mod 2).

==> f(n) = (n^2 - (n mod 2))/4

An alternative way is f(n) = floor(n^2/4), but the former is simpler to finish the second part:

f(s+t) - f(s-t) = ((s+t)^2 - (s-t)^2) / 4 + (((s-t) mod 2) - ((s+t) mod 2)) / 4.

The two moduli are always the same because s+t and s-t have the same parity, so the second part cancels out identically, leaving

f(s+t) - f(s-t) = ((s+t)^2 - (s-t)^2) / 4 = 4st / 4 = st.

Answer 4

I would start by splitting it into

0 + (1+2+3+...) + (1+2+3+...)

I think you would have to rhen look if n were odd or even.

In the brackets is just the sum of the natural numbers for which there is a formula, you would have to sum them up to n/2 or (n+1)/2 ???

Answer 5

f(n) = (n - 1)/2 if n is odd,

      = n/2   if n is even.

Hence

f(2k -1) = k - 1

f(2k) = k For every k =1, 2, 3, ....

For the "prove that" part one has to discuss several cases

s= even, t = even

s = odd, t = even

s = even, t = odd,

s = odd, t = even. But this works.