The sequence satisfies
for all nonnegative integers n,m and . If , determine
Table Of Content
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.
Your first impulse may be to set , let’s skip that for now. Instead, we look at the case of
That’s just great.
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 .
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.
This extends directly from .
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.
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.
This concludes our proof that .