11449 *Find the maximum and minimum values of f=(a ^{3}+b^{3}+c^{3})^{2}/((a^{2}+b^{2})(a^{2}+c^{2})(b^{2}+c^{2}))
given that a,b,c are positive and a+b≥c and a+c≥b and b+c≥a.*

__Solution:__

The domain of f is the part of the open first octant of a,b,c-space that is inside the infinite tetrahedron with faces a+b=c, a+c=b, b+c=a.

Now f is constant on each open straight half line that starts from (0,0,0) and stays in the domain.

So we only have to consider values in a+b+c=1 with a∈(0,1/2], b∈(0,1/2], a+b∈[1/2,1).

I did this with Maple and found the global minimum 9/8 for a=b=c and the global maximum 2 for a=b=c/2 or a=c=b/2 or b=c=a/2.

First I had the range [9/8,2) in mind, considering (a,b,c)=(t,t,t) and (a,b,c)=(0,t,t) etcetera. Here (0,t,t) is not in the domain.

But then, much to my surprise, I discovered the value 2 for a=b=c/2 (etcetera).

(I suppose the proposer of the problem doesn't ask for nonglobal extreme values.)

11455 *Determine the triangles T of maximal area in the Cartesian plane with the property that for all nonzero integer pairs (m,n) the interiors of T and T+(m,n) are disjoint.*

__Partial solution:__

I think I found a triangle T with a large area among the ones that meet the conditions, although I don't know whether T is optimal.

It's the equilateral triangle with vertices (0,0) and (ρ,ρ) with sides going through (1,0) and (ρ,ρ-1).

Then ρ=tan(75)/(1+tan(75)), where tan(75)=√((1/2+(1/4)*√3)/(1/2-(1/4)*√3)).

So the area of T is (1/4)*√3*2*(tan(75)/(1+tan(75)))^{2}.

This is about 0.538675..

11477

__Solution:__

I first ran a simulation program:

program frog;

var t,k,m,n:integer; a:array[0..30000,0..30000] of integer;

begin

while true do begin

writeln('n?'); readln(n);

for t:=0 to 30000 do for k:=0 to n do a[t,k]:=0;

for m:=1 to 30000 do

begin

k:=0; a[0,0]:=a[0,0]+1;

for t:=1 to 30000 do

begin

if not random≥1-k/n then k:=k-1 else k:=k+1;

a[t,k]:=a[t,k]+1

end

end;

for k:=0 to n do

writeln('limprobodd[',k:3,'] = ', (a[29999,k]/30000):13:10, ' limprobeven[',k:3,'] = ',(a[30000,k]/30000):13:10);

writeln; readln; writeln end

end.

I studied the output and noticed:

1) After an even number of hops, the frog is in a box with an even number, and after an odd number of hops in a box with an odd number, so

lim p_{2t}(k) = 0 iff k is odd and lim p_{2t+1}(k) = 0 iff k is even.

2) For each n the table of limits (p_{2t+1}(k),p_{2t}(k)) is symmetric, because the probability of a hop to the right at the left side is equal to the probability of a hop to the left at
the right side.

For instance, for n=3 we have (0,1/4),(3/4,0),(0,3/4),(1/4,0) and for n=4 (0,1/8),(1/2,0),(0,3/4),(1/2,0),(0,1/8)

Then I found an exacter way to approximate the numerical values of the nonzero limits:

program frog2;

var k,n,t:integer; p:array[0..100,0..30000] of real;

begin

while true do begin

writeln('n?'); readln(n);

for k:=0 to 100 do p[k,0]:=0;

p[0,0]:=1;

for t:=1 to 30000 do

begin

for k:=1 to n-1 do p[k,t]:=(1-(k-1)/n)*p[k-1,t-1]+((k+1)/n)*p[k+1,t-1]

end;

for k:=0 to n do writeln(p[k,29999]:13:10,'*',p[k,30000]:13:10);

writeln; end

end.

Now I thought I had to sum over all possible paths to box k to find the exact values.

But, thinking it over, I found I only had to solve a system of linear equations (for k=0,1,...,n):

(For odd k let p_{k}:=lim p_{2t+1}(k) and for even k let p_{k}:=lim p_{2t}(k).)

(For convenience, let p_{-1} = p_{n+1} := 0.)

p_{k} = p_{n-k},

p_{k} = (1-(k-1)/n)*p_{k-1} + ((k+1)/n)*p_{k+1}

SUM(k even: p_{k}) = 1 = SUM(k odd: p_{k})

I noticed that we can solve this system of linear equations for any fixed n.

For instance, I found for n=4 for the eventime limits (1/8,0,3/4,0,1/8) and for the oddtime limits (0,1/2,0,1/2,0), as I did earlier above.

For n=5 I found for the eventime limits (1/16,0,5/8,0,5/16,0) and for the oddtime limits (0,5/16,0,5/8,0,1/16).

Now I still had to find the solution for the general case.

Working from k=1 to greater k, I soon discovered p_{k} = (n over k)*p_{0}.

Then, using SUM(k even: p_{k}) = 1 = SUM(k odd: p_{k}), I finally found p_{k} = (n over k)*2^{1-n}.

11500 *We have n balls, labeled 1 through n, and n urns, also labeled 1 through n. Ball 1 is put into a randomly chosen urn. Thereafter, as j
increments from 2 to n, ball j is put into urn j if that urn is empty, otherwise, it is put into a randomly chosen empty urn. Let the random variable X be
the number of balls that end up in the urn bearing their own number. Show that the expected value of X is n - H _{n-1}.*

__Solution:__

First I ran the following program:

program urns;

var j,n,keuze,aantal:0..10; som,t,x:real; klaar:boolean; urn:array[1..10] of 0..10;

begin

som:=0; t:=0; writeln; writeln('n?'); readln(n);

while true do

begin

t:=t+1;

for j:=1 to n do urn[j]:=0;

keuze:=random(n)+1;

urn[keuze]:=1;

for j:=2 to n do

if urn[j]=0 then urn[j]:=j

else

begin

klaar:=false;

repeat

keuze:=random(n)+1;

if urn[keuze]=0 then begin urn[keuze]:=j; klaar:=true end

until klaar=true

end;

aantal:=0;

for j:=1 to n do if urn[j]=j then aantal:=aantal+1;

som:=som+aantal;

x:=som/t;

writeln(x:13:10)

end

end.

Looking at the output, I discovered H_{n} must denote 1+1/2+1/3+...+1/n.

Now how do we calculate the expected value?

E(X) = SUM(j:=1 to n; P(ball j in urn j)) = ...

P(ball 1 in urn 1) = 1/n.

P(ball 2 in urn 2) = 1 - 1/n

P(ball 3 in urn 3) = 1 - P(ball 1 in urn 3) - P(ball 2 in urn 3) = 1 - 1/n - 1/(n(n-1)) = 1 - 1/(n-1)

P(ball 4 in urn 4) = 1 - P(ball 1 in urn 4) - P(ball 2 in urn 4) - P(ball 3 in urn 4) = 1 - 1/n - 1/(n(n-1)) - 1/((n-1)(n-2)) = 1 - 1/(n-2)

P(ball 5 in urn 5) = 1 - P(ball 1 in urn 5) - P(ball 2 in urn 5) - P(ball 3 in urn 5) - P(ball 4 in urn 5) = 1 - 1/n - 1/(n(n-1)) - 1/((n-1)(n-2)) - 1/((n-2)(n-3)) = 1 - 1/(n-3)

... etc.

P(ball j in urn j) = 1 - 1/(n-(j-2))

P(ball n in urn n) = 1 - 1/2

So E(X) = n-1 - (1/2 + 1/3 + .. + 1/(n-1)) = n - H_{n-1}.

11565 *Let U1,U2,... be independent random variables, each uniformly distributed on [0,1].
a) For x in (0,1], let Nx be the least n such that SUM(k from 1 to n:√Uk) is greater than x. Find the expected value of Nx.
b) For x in (0,1], let Mx be the least n such that PRODUCT(k from 1 to n:Uk) is less than x. Find the expected value of Mx.*

__Solution:__

a) (From the output of a Pascal program, I guess E(Nx) must be something like 1+x^{2}, but for larger x a bit more.)

E(Nx) = SUM(n from 1 to ∞: n*P(Nx=n) = P(√u1 > x) + 2*P((√u1 ≤ x) and (√u1+√u2 > x)) + 3*P((√u1+√u2 ≤ x) and (√u1+√u2+√u3 > x)) + 4*P((√u1+√u2+√u3 ≤x) and (√u1+√u2+√u3+√u4 > x)) + ...

= 1-x^{2} + 2(x^{2} - INT(u1 from 0 to x^{2}: (x-√u1)^{2})) +
3(INT(u1 from 0 to x^{2}: (x-√u1)^{2}) - INT(u1 from 0 to x^{2} and u2 from 0 to (x-√u1)^{2}: (x-√u1-√u2)^{2}))
+ 4(INT(u1 from 0 to x^{2} and u2 from 0 to (x-√u1)^{2}: (x-√u1-√u2)^{2})) -
INT(u1 from 0 to x^{2} and u2 from 0 to (x-√u1)^{2} and u3 from 0 to (x-√u1-√u2)^{2}): (x-√u1-√u2-√u3)^{2})) + ...

= 1 + x^{2} + INT(u1 from 0 to x^{2}: (x-√u1)^{2}) + INT(u1 from 0 to x^{2} and u2 from 0 to (x-√u1)^{2}: (x-√u1-√u2)^{2}) +
INT(u1 from 0 to x^{2} and u2 from 0 to (x-√u1)^{2} and u3 from 0 to (x-√u1-√u2)^{2}): (x-√u1-√u2-√u3)^{2}) + ...

We can calculate these integrals from the inside through the outside by substituting √uk = vk and integrating by parts, and get

1 + x^{2} + (2/(3*4))x^{4} + ((2*2)/(3*4*5*6))x^{6} + ((2*2*2)/(3*4*5*6*7*8))x^{8} + ... = SUM( n from 0 to ∞: (x√2)^{2n}/(2n)!) = cosh(x√2).

b) E(Mx) = SUM(n from 1 to ∞: n*P(Mx=n)) = P(u1 < x) + 2*P((u1 ≥ x) and (u1*u2 < x)) + 3*P((u1*u2 ≥ x) and (u1*u2*u3 < x)) + 4*P((u1*u2*u3 ≥ x) and (u1*u2*u3*u4 < x)) + ...

= x + 2*INT(u1 from x to 1: x/u1) + 3*INT(u1 from x to 1 and u2 from x/u1 to 1: x/(u1*u2)) + 4*INT(u1 from x to 1 and u2 from x/u1 to 1 and u3 from x/(u1*u2) to 1: x/(u1*u2*u3)) + ...

= x - 2*x*ln(x) +(3/2)*x*ln^{2}(x) - (4/(2*3))*x*ln^{3}(x) + (5/(2*3*4))*x*ln^{4}(x) + ...

= x*SUM(n from 0 to ∞: ((n+1)/(n!))*(-ln(x))^{n}) = ... = 1 - ln(x).

(This agrees with the output of the Pascal program for x=1/e, which seems to fluctuate around 2.)

11570 *Alice and Bob play a number game. Starting with a positive number n, they take turns changing the number; Alice goes first.
Each player in turn may change the current number k to either k-1 or roundupward(k/2). The person who changes 1 to 0 wins. For which initial n does Alice have a winning strategy?*

__Solution:__

We find the good n up to N by the following procedure:

good[1]:=true;

for n:=2 to 2*N-2 do good[n]:=false;

for n:=2 to N-1 do if not good[n] then begin good[n+1]:=true; good[2*n-1]:=true; good[2*n]:=true end;

for n:=1 to N do if good[n] then writeln(n,' is good') else writeln(n,' is not good')

11572 *Given a circle C and two points A and B outside C, give an Euclidean construction to find a point P on C such that if Q and S are the second intersections with C of AP and BP respectively,
then QS is perpendicular to AB. (Special configurations, including the case that A and B and the center of C are collinear, are excluded.)*

__Partial solution:__

(Using Cabri, we can see that such a P does probably exist in most of the cases.)

Let A(a,c), B(b,c), P(cos(t),sin(t)), Q(cos(u),sin(u)), S(cos(u),-sin(u)) (, so AB is perpendicular to QS.)

We must have

1) A,P,Q collinear, which amounts to (cos(t)-a)(sin(u)-c) = (cos(u)-a)(sin(t)-c),

2) B,P,S collinear, which amounts to (cos(t)-b)(-sin(u)-c) = (cos(u)-b)(sin(t)-c).

We can eliminate u from 1) and 2) and find a polynomial p(x) of degree 6 with coefficients expressed in a,b,c such that p(sin(t))=0.

So we have to construct, with compass and straightedge only, the roots of p(x).

But p(x) looks awkward.

11573 *A Sudoku Permutation Matrix (SPM) of order n ^{2} is a permutation matrix of order n^{2} with exactly one 1 in each of the n^{2} submatrices obtained by partitioning
the original matrix into an n-by-n array of submatrices. Thus, for n=2, the permutation 1324 yields an SPM, but the identity permutation 1234 does not. Find the number of SPMs of order n^{2}.*

__Solution:__

First we count the number of SPMs of order n^{2} with n=2. The outcome is 16.

Next we look at SPMs of order n^{2} with n=3. Then, generalizing, we see:

The permutation π yields an SPM iff for all k∈{1,2,..n} the sequence π((k-1)n+1), π((k-1)n+2), ..., π(kn), contains exactly one element from each of the n sets
{(k-1)n+1, (k-1)n+2, ..., kn} with k∈{1,2,..n}.

Counting the number of possibilities for π(1), π(2), π(3), ... π(n^{2}), respectively, we find in the end that the number of possible permutations (and hence the number of possible
SPMs) is:

Π(i,j∈{1,2,..,n} : n^{2}-(i+j-2)n+(i-1)(j-1))) = Π(i,j∈{1,2,..n}:(n-(i-1))(n-(j-1))) = (n!)^{2n}. (So this outcome must be less than (n^{2})!.)

11623 *A fair coin is tossed n times and the results recorded as a bit string. A run is a maximal subsequence of identical tosses. Let the random variable X _{n} be the number of runs in the bit string not
immediately followed by a longer run. Find E(X_{n}).*

__Solution:__

E(X_{n}) = SUM(k from 1 to n: (n-1 over k-1)*(1+(k-1)*((1/2)*(1-prob)+prob)))/2^{n-1}, where

2^{n-1} is the number of compositions of n,

(n-1 over k-1) is the number of compositions of n in k parts;

the term 1 counts the last part (which will never be followed by a larger part);

for the other k-1 parts holds that they either will be followed by an equal part (with a chance we denote by prob),

or in half of the cases by a smaller part.

Because SUM(k from 1 to n: (n-1 over k-1)) = 2^{n-1} and SUM(k from 1 to n: (k-1)*(n-1 over k-1)) = (n-1)*2^{n-2}, we find

E(X_{n}) = 1 + (n-1)/4 + (1/2^{n})*SUM(k from 1 to n: (n-1 over k-1)*(k-1)*prob).

In this last sum, the term with k=2 is e/2^{n} where e=1 if n is even and e=0 if n is odd. We find

E(X_{n}) = 1 + (n-1)/4 + e/2^{n} + (1/2^{n})*SUM(k from 3 to n: SUM(m from 1 to int((n-(k-2))/2): (k-1)*(n-2m-1 over k-3))), where

(n-2m-1 over k-3) is the number of compositions of n-2m in k-2 parts.

This last doublesum can be calculated by changing the order of summation. With p:=int((n-1)/2) we get

SUM(m from 1 to p: SUM(k from 3 to n-2m+2: (k-1)*(n-2m-1 over k-3))) =

SUM(m from 1 to p: SUM(j from 0 to n-2m-1: (j+2)*(n-2m-1 over j))) =

SUM(m from 1 to p: 2^{n-2m} + (n-2m-1)*2^{n-2m-2}) =

(2^{n}+(n-1)*2^{n-2})*(1-(1/4)^{p})/3 - 2^{n-1}*SUM(m from 1 to p: m*(1/4)^{m}), so

E(X_{n}) = (n+3)/4 + e/2^{n} + ((n+3)/12)*(1-(1/4)^{p}) -(2/9)*(1+p*(1/4)^{p+1}-(p+1)*(1/4)^{p}))

where p:=int((n-1)/2) and e:=1 if n is even and e:=0 if n is odd

(This outcome should be equal to 199/64 for n=7, and it is.)

11635 *Let ABCD be a convex quadrilateral and M a point on the diagonal BD. Suppose that the perimeters of triangles ABM and BCM are equal, and likewise those of ADM and DCM.
Prove that AB = BC and AD = DC.*

__Solution:__

If not, the situation would be like in the following picture (with either (F=A and G=C) or (F=C and G=A)):

where x is positive and, in view of the conditions on the perimeters, GM = f-x.

Then GM is smaller than F'M = f, which is clearly impossible.

(Draw the circles through F' with centers B, M and D; since G is outside the first and the third, it must be outside the second.)

11656 *The sign chart of a polynomial f with real coefficients is the list of successive pairs of (f ',f) on the intervals separating real zeros of ff ', together with the signs at the zeros of ff '
themselves, read from left to right. Thus, for f = x ^{3} - 2x^{2}, the sign chart is ((1,-1),(0,0),(-1,-1),(0,-1),(1,-1),(1,0),(1,1)).
As a function of n, how many sign charts occur for polynomials of degree n?*

__Partial solution:__

We have the following possibilities for a point on the graph of f where the tangent is horizontal:

1) positive local minimum, corresponding to a zero of f ' with odd multipicity;

2) zero local minimum, corresponding to a zero of f ' with odd multipicity;

3) negative local minimum, corresponding to a zero of f ' with odd multipicity;

4) positive reflection point where f is descending, corresponding to a zero of f ' with even multipicity;

5) zero reflection point where f is descending, corresponding to a zero of f ' with even multipicity;

6) negative reflection point where f is descending, corresponding to a zero of f ' with even multipicity;

7) positive reflection point where f is ascending, corresponding to a zero of f ' with even multipicity;

8) zero reflection point where f is ascending, corresponding to a zero of f ' with even multipicity;

9) negative reflection point where f is ascending, corresponding to a zero of f ' with even multipicity;

10) positive local maximum, corresponding to a zero of f ' with odd multipicity;

11) zero local maximum, corresponding to a zero of f ' with odd multipicity;

12) negative local maximum, corresponding to a zero of f ' with odd multipicity;

On the graph of f, if one of these points is followed by another, we have the following posibilities:

A point of kind 1) may be followed by one of kind 10 or 7;

A point of kind 2) may be followed by one of kind 10 or 7;

A point of kind 3) may be followed by one of kind 7 through 12;

A point of kind 4) may be followed by one of kind 1 through 6;

A point of kind 5) may be followed by one of kind 3 or 6;

A point of kind 6) may be followed by one of kind 3 or 6;

A point of kind 7) may be followed by one of kind 10 or 7;

A point of kind 8) may be followed by one of kind 10 or 7;

A point of kind 9) may be followed by one of kind 7 through 12;

A point of kind 10) may be followed by one of kind 1 through 6;

A point of kind 11) may be followed by one of kind 3 or 6;

A point of kind 12) may be followed by one of kind 3 or 6.

Hence we may count the number of sign charts with the following pascal program, using recursion:

(n is the degree of f, g is the maximal degree of a positive definite factor of f ', sommult is the sum of the multiplicities of zeros of f ',
laatste is the last considered point of one of kinds 1) through 12), a is the number of sign charts.)

program opl11656;

var n,m,g,sommult,laatste:integer; a:real;

procedure byzpunten(var sommult,laatste:integer);

var j,k,sm,tm:integer;

begin

sm:=sommult;

if laatste=1 then

begin

for k:=1 to n-1-sm do if (k mod 2)=1 then

begin

sommult:=sommult+k;

if sommult=n-1 then a:=a+1 else

begin

tm:=sommult;

laatste:=10; byzpunten(sommult,laatste);

laatste:=7; sommult:=tm; byzpunten(sommult,laatste)

end

end

end;

if laatste=2 then

begin

for k:=1 to n-1-sm do if (k mod 2)=1 then

begin

sommult:=sommult+k;

if sommult=n-1 then a:=a+1 else

begin

tm:=sommult;

laatste:=10; byzpunten(sommult,laatste);

laatste:=7; sommult:=tm; byzpunten(sommult,laatste)

end

end

end;

if laatste=3 then

begin

for k:=1 to n-1-sm do if (k mod 2)=1 then

begin

sommult:=sommult+k;

if sommult=n-1 then a:=a+1 else

begin

tm:=sommult;

for j:=7 to 12 do

begin sommult:=tm; laatste:=j; byzpunten(sommult,laatste) end;

end

end

end;

if laatste=4 then

begin

for k:=1 to n-1-sm do if (k mod 2)=0 then

begin

sommult:=sommult+k;

if sommult=n-1 then a:=a+1 else

begin

tm:=sommult;

for j:=1 to 6 do

begin sommult:=tm; laatste:=j; byzpunten(sommult,laatste) end;

end

;end

end;

;if laatste=5 then

begin

for k:=1 to n-1-sm do if (k mod 2)=0 then

begin

sommult:=sommult+k;

if sommult=n-1 then a:=a+1 else

begin

tm:=sommult;

laatste:=3; byzpunten(sommult,laatste);

laatste:=6; sommult:=tm; byzpunten(sommult,laatste)

end

end

end;

if laatste=6 then

begin

for k:=1 to n-1-sm do if (k mod 2)=0 then

begin

sommult:=sommult+k;

if sommult=n-1 then a:=a+1 else

begin

tm:=sommult;

laatste:=3; byzpunten(sommult,laatste);

laatste:=6; sommult:=tm; byzpunten(sommult,laatste)

end

end

end;

if laatste=7 then

begin

for k:=1 to n-1-sm do if (k mod 2)=0 then

begin

sommult:=sommult+k;

if sommult=n-1 then a:=a+1 else

begin

tm:=sommult;

laatste:=10; byzpunten(sommult,laatste);

laatste:=7; sommult:=tm; byzpunten(sommult,laatste)

end

end

end;

if laatste=8 then

begin

for k:=1 to n-1-sm do if (k mod 2)=0 then

begin

sommult:=sommult+k;

if sommult=n-1 then a:=a+1 else

begin

tm:=sommult;

laatste:=10; byzpunten(sommult,laatste);

laatste:=7; sommult:=tm; byzpunten(sommult,laatste)

end

end

end;

if laatste=9 then

begin

for k:=1 to n-1-sm do if (k mod 2)=0 then

begin

sommult:=sommult+k;

if sommult=n-1 then a:=a+1 else

begin

tm:=sommult;

for j:=7 to 12 do

begin sommult:=tm; laatste:=j; byzpunten(sommult,laatste) end;

end

end

end;

if laatste=10 then

begin

for k:=1 to n-1-sm do if (k mod 2)=1 then

begin

sommult:=sommult+k;

if sommult=n-1 then a:=a+1 else

begin

tm:=sommult;

for j:=1 to 6 do

begin sommult:=tm; laatste:=j; byzpunten(sommult,laatste) end;

end

;end

end;

if laatste=11 then

begin

for k:=1 to n-1-sm do if (k mod 2)=1 then

begin

sommult:=sommult+k;

if sommult=n-1 then a:=a+1 else

begin

tm:=sommult;

laatste:=3; byzpunten(sommult,laatste);

laatste:=6; sommult:=tm; byzpunten(sommult,laatste)

end

end

end;

if laatste=12 then

begin

for k:=1 to n-1-sm do if (k mod 2)=1 then

begin

sommult:=sommult+k;

if sommult=n-1 then a:=a+1 else

begin

tm:=sommult;

laatste:=3; byzpunten(sommult,laatste);

laatste:=6; sommult:=tm; byzpunten(sommult,laatste)

end

end

end;

end{byzpunten};

begin

for n:=1 to 30 do

begin

if ((n-1) mod 2)=0 then a:=1 else a:=0;

for g:=0 to n-2 do if (g mod 2)=0 then

for m:=1 to 6 do

begin sommult:=g; laatste:=m; byzpunten(sommult,laatste) end;

a:=2*a; writeln(n:4,a:13:0)

end

end.

The output comes quickly for n from 1 through 20, slowly for n from 21 through 23, and too slowly or not at all for n at least 24.

The results (n,a) are as follows:

(1,2), (2,6), (3,18), (4,48), (5,128), (6,336), (7,882), (8,2310), (9,6050), (10,15840), (11,41472), (12,108576), (13,284258), (14,744198), (15,1948338), (16,5100816),

(17,13354112), (18,34961520), (19,91530450), (20,239629830), (21,627359042), (22,1642447296), (23,4299982848), (24,11257501248), (25,29472520898), ...

I discovered, denoting the a that belongs to n by a_{n}:

if a_{2m+1}/a_{2m} = p/q (lowest terms), then both a_{2m+2}/a_{2m+1} and a_{2m+3}/a_{2m+2} are equal to (p^{2}-1)/(pq).

The sequence of factors 3, 8/3, 21/8, 55/21, 144/55, 377/144, 987/377, ... seems to tend to 2.618... = (3+√5)/2.

We now see that the sequence a_{n} begins as follows:

2*1*1, 2*1*3, 2*3*3, 2*3*8, 2*8*8, 2*8*21, 2*21*21, 2*21*55, 2*55*55, 2*55*144, 2*144*144, 2*144*377, 2*377*377, 2*377*987, ...

Here we can decompose the sequence 1,3,8,21,55,144,377,987, ... as follows: 1*1, 1*3, 2*4, 3*7, 5*11, 8*18, 13*29, 21*47, ... so it is the product of two Fibonacci sequences.

If we denote by F the Fibonacci sequence 1,1,2,3,5,8,13,21, ... and by G the Fibonacci sequence 1,3,4,7,11,18,29,47, ...
and by x the product with x_{m}:=F_{m}*G_{m},

then we find x_{m}=F_{2m} and (for these low values of m):

a_{2m-1} = 2*x_{m}*x_{m} and a_{2m} = 2*x_{m}*x_{m+1}.

To prove with induction that this holds for all natural m, we still need some combinatorial argument that explains why for all natural m should hold

a_{2m+1}/a_{2m} = a_{2m}/a_{2m-1} = F_{2m+2}/F_{2m}.

(O.P.Lossers suggests the sequence is also generated by the recurrence a_{n+1} - a_{n-1} = 2F_{2n}.)

** Earlier solutions 1:** click here .

** Earlier solutions 2:** click here .

** Earlier solutions 3:** click here .

** Earlier solutions 4:** click here .

** Earlier solutions 5:** click here .

** More solutions:** click here