1

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$

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

mathophile
  • 3,225

2 Answers2

3

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)$.

Oleksandr Kulkov
  • 843
  • 1
    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. – Paramanand Singh Dec 26 '23 at 01:46
  • Is there a source I can read for differentiation tricks for generating functions? – qwr Dec 27 '23 at 02:58
  • You can try https://codeforces.com/blog/entry/76447. I think they might also be mentioned in some van der Hoeven papers? – Oleksandr Kulkov Dec 27 '23 at 11:09
1

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.

sku
  • 2,643