Proving a recurrence relation involving n choose r

Question

I am trying to prove some recurrence relations regarding these 2 series:

1. $$O_n = \sum_{r=0}^n \binom{2n+1-r}{r}$$
2. $$E_n= \sum_{r=0}^n \binom{2n-r}{r}$$

The recurrence relations being:

1. $$T_n = 3T_{n-1} - T_{n-2}$$ where T can be interchanged with O or E
2. $$O_{n-1}= \frac{O_{n-2}+E_{n}}{2}$$

I have tried everything from trying to apply Pascal's identity to trying induction but nothing worked.

Answer 1

For the second one we may also compute an auxiliary generating function to start. We get

$$T(x) = \sum_{n\ge 0} x^{2n+1} \sum_{r=0}^n {2n+1-r\choose r} = \sum_{r\ge 0} \sum_{n\ge r} {2n+1-r\choose r} x^{2n+1} \\ = \sum_{r\ge 0} x^{2r} \sum_{n\ge 0} {2n+1+r\choose r} x^{2n+1} \\ = \sum_{r\ge 0} x^{2r} \sum_{n\ge 0} {n+r\choose r} \frac{1}{2} (1-(-1)^n) x^n \\ = \sum_{r\ge 0} x^{2r} \frac{1}{2} \left[ \frac{1}{(1-x)^{r+1}} - \frac{1}{(1+x)^{r+1}} \right] \\ = \frac{1}{2} \frac{1}{1-x} \frac{1}{1-x^2/(1-x)} - \frac{1}{2} \frac{1}{1+x} \frac{1}{1-x^2/(1+x)} \\ = \frac{1}{2} \frac{1}{1-x-x^2} - \frac{1}{2} \frac{1}{1+x-x^2} = \frac{x}{x^4-3x^2+1}.$$

Now we have

$$[x^{2n+1}] \frac{x}{x^4-3x^2+1} = [x^{2n}] \frac{1}{x^4-3x^2+1} = [x^n] \frac{1}{x^2-3x+1}$$

and that is therefore our generating function $S(x).$ Using exactly the same computation as in the first answer we once more find

$$\bbox[5px,border:2px solid #00A000]{ S_n = 3 S_{n-1} - S_{n-2}.}$$

This is the claim. It remains to show that

$$O_{n-1} = \frac{1}{2} O_{n-2} + \frac{1}{2} E_n.$$

This is

$$[x^{n-1}] \frac{1}{x^2-3x+1} = \frac{1}{2} [x^{n-2}] \frac{1}{x^2-3x+1} + \frac{1}{2} [x^n] \frac{1-x}{x^2-3x+1}.$$

or alternatively

$$[x^n] \frac{x}{x^2-3x+1} = \frac{1}{2} [x^n] \frac{x^2}{x^2-3x+1} + \frac{1}{2} [x^n] \frac{1-x}{x^2-3x+1}.$$

The RHS is

$$\frac{1}{2} [x^n] \left[1+\frac{3x-1}{x^2-3x+1}\right] + \frac{1}{2} [x^n] \frac{1-x}{x^2-3x+1}.$$

With $n\ge 2$ this becomes

$$\frac{1}{2} [x^n] \frac{3x-1}{x^2-3x+1} + \frac{1}{2} [x^n] \frac{1-x}{x^2-3x+1} = [x^n] \frac{x}{x^2-3x+1}.$$

This concludes the argument.

Answer 2

For the first one we may compute an auxiliary generating function to start. We get

$$T(x) = \sum_{n\ge 0} x^{2n} \sum_{r=0}^n {2n-r\choose r} = \sum_{r\ge 0} \sum_{n\ge r} {2n-r\choose r} x^{2n} \\ = \sum_{r\ge 0} x^{2r} \sum_{n\ge 0} {2n+r\choose r} x^{2n} \\ = \sum_{r\ge 0} x^{2r} \sum_{n\ge 0} {n+r\choose r} \frac{1}{2} (1+(-1)^n) x^n \\ = \sum_{r\ge 0} x^{2r} \frac{1}{2} \left[ \frac{1}{(1-x)^{r+1}} + \frac{1}{(1+x)^{r+1}} \right] \\ = \frac{1}{2} \frac{1}{1-x} \frac{1}{1-x^2/(1-x)} + \frac{1}{2} \frac{1}{1+x} \frac{1}{1-x^2/(1+x)} \\ = \frac{1}{2} \frac{1}{1-x-x^2} + \frac{1}{2} \frac{1}{1+x-x^2} = \frac{1-x^2}{x^4-3x^2+1}.$$

Now we have

$$[x^{2n}] \frac{1-x^2}{x^4-3x^2+1} = [x^n] \frac{1-x}{x^2-3x+1}$$

and that is therefore our generating function $S(x).$ At this time we may conclude by inspection. If more detail is required write

$$[x^n] S(x) (x^2-3x+1) = [x^n] (1-x).$$

We thus have for $n\ge 2$

$$S_{n-2} - 3 S_{n-1} + S_n = 0$$

or

$$\bbox[5px,border:2px solid #00A000]{ S_n = 3 S_{n-1} - S_{n-2}.}$$

This is the claim. The initial values are found using the same coefficient extractor, which gives with $n=0$ that $S_0 = 1$ and with $n=1$ that $-3 S_0 + S_1 = -1$ or $S_1 = 2.$