Close Menu Navigation

# Square Sequence

The sequence satisfies

for all nonnegative integers n,m and . If , determine

### 1. The sad shit

Everytime I see problems. like. this., I just go like “oh fuck.” And it’s for good reasons too, because there are usually very few “techniques” in general that can be used to solve generic functional equations. Anyways, enough with the sad shit, let’s move on

### 2. Moving on…

We first probe the system for some general properties. We know that , but as the problem suggests, we should check out what is.

#### Finding

Your first impulse may be to set , let’s skip that for now. Instead, we look at the case of

That’s just great.

#### Finding

Now that we’re rolling, let’s probe the system a little further. Setting , we see that

In fact, this seems to suggest an interesting property about .

#### Show that

This can be easily shown by construction. Set and , our equation becomes

Awesome, let’s generate some more numbers from what we have

Hmm, seems like for , but we don’t have a good spread on the generated numbers yet, so let’s keep on going.

#### Show that

This extends directly from .

#### Finding

Since we only know , we can only generate in terms of these known terms. We observe that for , this satisfies our criterion. Set

Interestingly enough, this fits in with the previous observation that for , . Let’s make one last probe at the system to be sure.

#### Finding

We’ve already generated from the generating class of so we now turn our attention to finding using only . Again, we observe that satisfies this property.

Whelp, that’s good enough for me. Let’s buckle down and prove once and for all that ; but first, we derive an even more general recurrence that exhibits trivial monotone properties in its indices that is suitable for inductive proofs. We apply the observations made from finding and .

As per and , set

### 3. Show that

We will show this inductively on the naturals . Informally, we will use the identity to form the foundation of the inductive steps.

Suppose , as we’ve already established, , we now outline the inductive steps.

Show that

This concludes our proof that .

Woosh