# If $(1+px+x^2)^n=1+a_{1}x+a_{2} x^2+....+a_{2n}x^{2n}$, then prove that $(np-pr)a_{r}=(r+1)a_{r+1}+(r-1-2n)a_{r-1}$ for $1<r<2n$

If $$(1+px+x^2)^n=1+a_{1}x+a_{2} x^2+....+a_{2n}x^{2n}$$, then prove that $$(np-pr)a_{r}=(r+1)a_{r+1}+(r-1-2n)a_{r-1}$$ for $$1

My try:

I tried putting $$r=2$$ and solved the problem and verfied the answer.

Then I tried to this for general

First I did was $$(np-pr)=\dfrac{(r+1)a_{r+1}}{a_{r}}+\dfrac{(r-1-2n)a_{r-1}}{a_r}$$, And i tried to solve coefficient of $$x^{r+1}$$ divided by coefficeint of $$x^r$$ but i lead me nowhere.

Any help here is appereciated.

Same kind of problem has been asked here For $(1+x+x^2)^n = A_0 + A_1x + ... + A_{2n}x^{2n}$, prove that $(n-r)A_r + (2n -r+1)A_{r-1} = (r+1)A_{r+1}$ but he is skipping some steps so I can't understand he is saying use induction and I've not studied indunction yet

Let $$Q(x) = P(x)^n$$. Then, differentiating both parts, we get

$$P(x) Q'(x) = nQ(x) P'(x).$$

In our case, $$Q(x) = a_0+a_1 x+\dots+a_{2n} x^{2n}$$ and $$P(x) = 1+px+x^2$$, so

$$(1+px+x^2)Q'(x) = n(2x+p)Q(x).$$

Now, extracting the coefficients near $$x^r$$ in the LHS and RHS, we get

$$(r+1)a_{r+1} + pra_r + (r-1)a_{r-1} = n(2a_{r-1}+p a_r),$$

which is equivalent to $$(r+1)a_{r+1} = (2n-r+1) a_{r-1} + p(n-r) a_r$$. $$\square$$

As you see, this approach allows to easily find P-recursive equations for any base $$P(x)$$.

• This is such a nice approach which avoid a lot of calculations. +1 Also let us observe that the idea of derivatives for polynomials can be defined algebraically and thus it doesn't really involve calculus. Dec 26, 2023 at 1:46
• Is there a source I can read for differentiation tricks for generating functions?
– qwr
Dec 27, 2023 at 2:58
• You can try codeforces.com/blog/entry/76447. I think they might also be mentioned in some van der Hoeven papers? Dec 27, 2023 at 11:09

First note that in the induction from $$n$$ to $$n+1$$, $$a_r$$ becomes $$a_r + pa_{r-1} + a_{r-2}$$. We need to prove:

$$((n+1)p - pr)(a_r + pa_{r-1} + a_{r-2}) = (r+1)(a_{r+1} + pa_r + a_{r-1}) + (r-1 - 2(n+1)) (a_{r-1} + pa_{r-2} + a_{r-3})$$

rearranging we get: $$\{\left((n+1)p - pr\right)a_r - [(r+1)a_{r+1} +\left(r-1 - 2(n+1)\right)a_{r-1}]\}+\{((n+1)p - pr)pa_{r-1} -[ (r+1)pa_r + (r-1 - 2(n+1))pa_{r-2}]\} + \{((n+1)p - pr)a_{r-2} - [(r+1)a_{r-1}) + \{r-1 - 2(n+1)\} a_{r-3})]\} = t_1 + t_2 + t_3 = 0$$

With some simplification we get:

$$t_1 = ((np - pr)a_r - [(r+1)a_{r+1} +\left(r-1 - 2n\right)a_{r-1}] + pa_r -2a_{r-1}$$

$$t_2 = ((np - p(r-1))pa_{r-1} - [p(ra_r + (r- 2 - 2n)a_{r-2})] - pa_r + pa_{r-2}$$

$$t_3 = ((np - p(r-2))pa_{r-2} - [p((r-1)a_{r-1} + (r- 3 - 2n)a_{r-3})] +2a_{r-1} -pa_{r-2}$$

In the sum $$t_1 + t_2 + t_3$$, the sum of the last two terms cancel out and the remaining three terms are zero by induction assumption.