# How to identify the coefficient of $x^k$ in $1/(1-x)^N$ where $N$ can be a large integer

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.

• Hint: Note that $\frac {d^n}{dx^n}A(x)=\frac 1{\left(1-x\right)^n}$. – lulu Nov 3 '16 at 16:33
• @lulu, don't you mean $\frac{1}{n!(1-x)^{n+1}}$? – Kyle Ferendo Nov 3 '16 at 16:37
• 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. – Kyle Ferendo Nov 3 '16 at 16:40
• 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. – Gabriel Burns Nov 3 '16 at 16:44
• @KyleFerendo Indeed I do. Thanks for the correction. – 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$.

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*}

Comment:

• 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

$$C_{n+1,N}=\sum_{j=0}^NC_{n,j}$$

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

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

$C_{2,0}=1,C_{2,1}=2,C_{2,2}=3,C_{2,3}=4,C_{2,4}=5$

$C_{3,0}=1,C_{3,1}=3,C_{3,2}=6,C_{3,3}=10,C_{3,4}=15$

$$C_{4,4}=1+3+6+10+15=35.$$

• man, I don't understand the way you separate C(n+1,i)Xi at third step – Antonio González Borrego Nov 3 '16 at 17:31
• 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. – Antonio González Borrego Nov 3 '16 at 19:02
• @AntonioGonzálezBorrego What about my formula. it gives $35$ for $n=4$ and $N=4$. – hamam_Abdallah Nov 4 '16 at 20:21