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

Question

I have an infinite series in the form $A(x) =\frac{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 over there using induction, but I didn't understand it. Please suggest a different solution or help me to understand the solution that uses induction.

Answer 1

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

Answer 2

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

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