Processing math: 100%

anayjoshi .com

Problem #5


[INMO-1996]: Define a sequence an by a1=1,a2=2, and an+2=2an+1an+2 for n>=1. Prove that for any m, amam+1 is also a term in the sequence.


Solution:

Polynomial equations are very closely linked with sequences. Let’s try to find a general expression for an. Since the recurrence relation has a depth of 2, a good guess is to assume an=pn2+qn+r. Matching the initial conditions forces:

p+q+r=1 4p+2q+r=2

We need one more equation to solve for p,q,r. Plugging the form of an into the given recurrence relation, we get

p(n+2)2+q(n+2)+r=2p(n+1)2+2q(n+1)+2rpn2qnr+2

The coeffient of n2 and n in both LHS and RHS turn out to be p and 4p+q respectively. But equating the constant term tells that p=1. Now, solving for q and r using the two equations mentioned before, we get q=2,r=2

an=n22n+2

Now that we know the general form of an, we can try to evaluate amam+1, which would turn out to be a fourth degree polynomial. Let’s now make a reasonable assumption: amam+1=as where s=xm2+ym+z for some constants x,y,z. The motivation for this guess is that we are trying to represent a fourth degree polynomial of m in terms of as. Throw in some number manipulation, and we get amam+1=am2m+2, which completes our proof.

Commentary:

On the surface, the assumptions taken in this solution might seem to be coming out of the blue. But I like to think of this problem as a nice example of System Identification. Engineers might especially be able to relate with this solution. In real world problems, engineers are often required to make intelligent guesses/models about the physical system which they are working on. An example is to guess the transfer function of an electronic circuitry based on some emperical data. Relating to this problem, if you try to play around with the given recurrence relation (which is akin to experimentation and gathering emperical data), you would quickly tend to make the assumption that an could be a quadratic expression of n.