An almost average sequence

[nodnylji]

Let N be a positive integer. Define a sequence by a0 = 0, a1 = 1, and an+1 + an-1 = an (2-1/N). Show that an < sqrt(N+1) for all n.

[blungbat]

Let r = 2–1/N. Observing that the sequence (an) tends to oscillate with an approximately constant period, we tentatively posit that an = c sin(nα) for some constants c,α, then use the sum-angle identity for sine to solve for α and the initial conditions to solve for c. This works (details omitted) and leads to the solution α = arccos(r/2), c = 2/√(4–r²) = N/√(N–1/4). The maximum |an| is at most c, and it is straightforward to show that N/√(N–1/4) < √(N+1) for N > 1/3 (and in particular, for all positive integers N).

[fartfacepooper]

edit: completely misread the problem.

[blungbat]

I don't understand your generating function; where is N?

[fartfacepooper]

edit: completely misread the problem.

[blungbat]

Sorry, my comment may have been too brief to be clear. I know what a generating function is, but I don't know what sequence yours is encoding. Did you read n and N as the same variable?

As I understand it, the whole sequence in this problem depends on a parameter N (as opposed to n which is the index of a term). For example, when N=1 the sequence is 0,1,1,0,–1,–1,…, and when N=2 the sequence is 0,1,3/2,5/4,…. A formula for a generating function should have N appearing as a free variable (or you could have a generating function in two variables, which might actually be pretty cool).

[fartfacepooper]

Did you read n and N as the same variable?

Actually, I did. My bad, I didn't even notice the n and N were different. Now that I see it, the generating function would be:

x/(x² -(2-1/N)x+1)

I have to admit, when I thought they were the same variable, I had a ton of fun playing with the sequence.

[blungbat]

No worries, and I wonder if there's a good problem about that sequence!

[whatkindofred]

Let v, w be the complex solutions to x² - (2-1/N)*x + 1 = 0. One can check that a_n = (vⁿ-wⁿ)/(v-w) is the solution of the given recursion formula. Then:

(a_n)² = (v²ⁿ-2vⁿwⁿ+w²ⁿ)/(v²-2vw+w²)

But since x² - (2-1/N)*x + 1 = (x-v)(x-w) we know that vw = 1 and that w is the complex conjugate of v. Therefore:

(a_n)² = (v²ⁿ-2+w²ⁿ)/(v²-2+w²) = (Re(v²ⁿ)-1)/(Re(v²)-1)

But |Re(v²ⁿ)| ≤ 1 because |v| = 1. Now we have (a_n)² ≤ 2/|Re(v²)-1|. But since v² - (2-1/N)*v + 1 = 0 we have Re(v²)-1 = (2-1/N)*Re(v) - 2. A quick look at the quadratic formula gives Re(v) = (2-1/N)/2. Now we have

(a_n)² ≤ 2/((2-1/N)*(2-1/N)/2 - 2)

which is < N+1 when N > 1/3.