I have an infinite serie in the form A(x) = 1/(1-x) which expanded is A(x) = 1 + x + x^2 + x^3... I need to find the coefficient of the term x^K in A(x)^N where N can be a large number(2^32). I saw a solution overthere using induction, but I didn't understand it. Please suggest a different solution or help me to understand the solution that uses induction.

  • $\begingroup$ Hint: Note that $\frac {d^n}{dx^n}A(x)=\frac 1{\left(1-x\right)^n}$. $\endgroup$ – lulu Nov 3 '16 at 16:33
  • $\begingroup$ @lulu, don't you mean $\frac{1}{n!(1-x)^{n+1}}$? $\endgroup$ – Kyle Ferendo Nov 3 '16 at 16:37
  • $\begingroup$ Let's try to get your induction started. What's the constant term in $A(x)^2$ going to be? $1$. What about the $x$ term? $1\cdot x + x \cdot 1 = 2x$. What about $x^2$? $1\cdot x^2 + x\cdot x + x^2\cdot 1 = 3x^2$. See a pattern? Now try to figure out $A(x)^3$, and look for another pattern. Once you think you've found the general pattern, try to prove it. $\endgroup$ – Kyle Ferendo Nov 3 '16 at 16:40
  • 1
    $\begingroup$ If you take $A(x)=1+x+x^2\dots$ to the $N^\text{th}$ power, you are multiplying $N$ copies of it together. By the rules of polynomial multiplication, this will be the sum of every possible product of one term from each copy. $x^k$ terms are products of terms whose exponents total $k$, so the coefficient is the same as the number of ways to write $N$ numbers from $0$ to $k$ totaling $k$, where the order matters. Don't know if that makes it easier or harder for you, but it's a different way of looking at it, anyway. $\endgroup$ – Gabriel Burns Nov 3 '16 at 16:44
  • 1
    $\begingroup$ @KyleFerendo Indeed I do. Thanks for the correction. $\endgroup$ – lulu Nov 3 '16 at 16:47

We can extract the coefficient of $x^k$ of $\frac{1}{(1-x)^N}$ by using the binomial series expansion with $\alpha = -N$.

\begin{align*} (1+x)^\alpha=\sum_{j=0}^\infty\binom{\alpha}{j}x^j\qquad\qquad |x|<1, \alpha\in\mathbb{C}\tag{1} \end{align*}

It is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series.

We obtain \begin{align*} [x^k]\frac{1}{(1-x)^N}&=[x^k](1-x)^{-N}\\ &=[x^k]\sum_{j=0}^\infty\binom{-N}{j}(-x)^j\tag{1}\\ &=[x^k]\sum_{j=0}^\infty\binom{N+j-1}{j}x^j\tag{2}\\ &=\binom{N+k-1}{k}\tag{3} \end{align*}


  • In (1) we apply the binomial series expansion (1) with $\alpha=-N$.

  • In (2) we use the binomial identity \begin{align*} \binom{-p}{q}=\binom{p+q-1}{q}(-1)^q \end{align*}

  • In (3) we select the coefficient of $x^k$.


For $i=0,1,2....$ put $\; C_{1,i}=1$.

Assume the following recurrence hypothesis

$$(A(x))^n=\sum_{i\in N}C_{n,i}x^i.$$

$$(A(x))^{n+1} =(A(x))^n\sum_{j\in N}x^j$$

$$=\sum_{i,j \in N}C_{n,i}C_{1,j}x^{i+j}$$

$$=\sum_{i\in N}(\sum_{j=0}^i C_{n,j})x^i$$

thus, we get the following recursive formula


with $C_{1,j}=1$ for $j=0,1,2...$.

For example, take $n=4,N=4$




  • $\begingroup$ man, I don't understand the way you separate C(n+1,i)Xi at third step $\endgroup$ – Antonio González Borrego Nov 3 '16 at 17:31
  • $\begingroup$ an example, A(x)^4 and I want to know the coefficient of x^4. When you use (N+1)^(n-1) equals 5^3 = 125, but the correct solution is 35 by using online calculator. $\endgroup$ – Antonio González Borrego Nov 3 '16 at 19:02
  • $\begingroup$ @AntonioGonzálezBorrego What about my formula. it gives $35$ for $n=4$ and $N=4$. $\endgroup$ – hamam_Abdallah Nov 4 '16 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.