# Issue w/ extracting coefficients from generating function using IDTFT

This q will make use of these 3 DTFT pairs... $$\require{extpfeil}\Newextarrow{\xleftrightarrow}{15,15}{0x2194} \begin{array}{rcl} \alpha x_1[n] + \beta x_2[n] & \xleftrightarrow{\mathscr{F}} & \alpha X_1[e^{j\omega}] + \beta X_2[e^{j\omega}]\\ x[n - n_o] & \xleftrightarrow{\mathscr{F}} & e^{-j\omega n_o}X[e^{j\omega}]\\ \left(\begin{array}{c}n+r-1\\n\end{array}\right)a^nu[n] & \xleftrightarrow{\mathscr{F}} & \frac{1}{\left(1 - a\text{e}^{-j\omega}\right)^r} \end{array}$$

My q actually stems from this one...

How do you find the number of solutions like this?

$$x_1 + x_2 + x_3 + x_4 = 32$$

where $$0 \le x_i \le 10$$.

What's the generalized approach for it?

To which I provided a generalized approach...

$$card\left(C\right) = \left[x^{n - vl}\right]\left(x^0 + x^2 + \cdots + x^{u - l}\right)^v = \left[x^{n - vl}\right]\left(\frac{1 - xx^{u - l}}{1 - x}\right)^v$$

As well as the answer to the given problem...

$$\Longrightarrow \left[x^{32 - 4\cdot 0}\right]\left(\frac{1 - xx^{10 - 0}}{1 - x}\right)^4 = 165$$

Wrt these definitions...

• # variables (NOT only 4) $$=v$$.
• Rhs (NOT only 32) $$=n$$.
• Lower bound (NOT only 0) $$=l$$.
• Upper bound (NOT only 10) $$=u$$.

I've since learned of the IDTFT$$\left[X[e^{j\omega}]\right]$$'s machine-like efficiency when used as a coefficient extractor, e.g., after assigning values for the 4 variables, the quoted sequence is represented by...

$$\left(x^0 + x^2 + \cdots + x^{10}\right)^4 = \left(\frac{1 - x^{11}}{1 - x}\right)^4$$

Which, after expanding...

$$= \frac{1}{(1-x)^4} -\frac{4x^{11}}{(1-x)^4} +\frac{6x^{22}}{(1-x)^4} -\frac{4x^{33}}{(1-x)^4} +\frac{x^{44}}{(1-x)^4}$$

& substituting $$e^{-j\omega}\;\forall\;x$$ (which of course, would seldom be done in practice, BUT aids explanation)...

$$= \frac{1}{(1-e^{-j\omega})^4} -\frac{4e^{-j11\omega}}{(1-e^{-j\omega})^4} +\frac{6e^{-j22\omega}}{(1-e^{-j\omega})^4} -\frac{4e^{-j33\omega}}{(1-e^{-j\omega})^4} +\frac{e^{-j44\omega}}{(1-e^{-j\omega})^4}$$

We treat it as the TF $$X[e^{j\omega}]$$ & VERY quickly deduce the final answer (using the 3 aforementioned DTFT pairs)...

$$\begin{array}{rcl} X[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & x[n]\\ \shortparallel & & \shortparallel\\ \frac{1}{(1-e^{-j\omega})^4} = X_1[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & x_1[n] = \left(\begin{array}{c}n+3\\n\end{array}\right)u[n]\\ + & & +\\ ? = X_2[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & x_2[n] =\;?\\ + & & +\\ \vdots & \vdots & \vdots\\ + & & +\\ ? = X_5[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & x_5[n] =\;?\\ & & \\ & \Downarrow & \\ & & \\ X[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & x[n]\\ \shortparallel & & \shortparallel\\ \frac{1}{(1-e^{-j\omega})^4} = X_1[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & x_1[n] = \left(\begin{array}{c}n+3\\n\end{array}\right)u[n]\\ - & & -\\ \frac{4e^{-j\omega11}}{(1-e^{-j\omega})^4} = 4e^{-j\omega11}X_1[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & 4x_1[n - 11] = 4\left(\begin{array}{c}n-8\\n\end{array}\right)u[n - 11]\\ + & & +\\ \frac{6e^{-j\omega22}}{(1-e^{-j\omega})^4} = 6e^{-j\omega22}X_1[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & 6x_1[n - 22] = 6\left(\begin{array}{c}n-19\\n\end{array}\right)u[n - 22]\\ - & & -\\ \frac{4e^{-j\omega33}}{(1-e^{-j\omega})^4} = 4e^{-j\omega33}X_1[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & 4x_1[n - 33] = 4\left(\begin{array}{c}n-30\\n\end{array}\right)u[n - 33]\\ + & & +\\ \frac{e^{-j\omega44}}{(1-e^{-j\omega})^4} = e^{-j\omega44}X_1[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & x_1[n - 44] = \left(\begin{array}{c}n-41\\n\end{array}\right)u[n - 44]\\ & & \\ & \Downarrow & \\ & & \\ \end{array}\\ x[n] = \frac{(n+1)(n+2)(n+3)u[n]}{6}$$

I've already verified to myself that $$x[n]$$ is a closed form version of the GF, i.e., $$(0,1,2,3,4,\ldots) \mapsto (1,4,10,20,30,\ldots)$$, but there are certain GFs - the generalized 1 that I opened up w/ for instance - which I struggle to find IDTFTs for!

Could someone please help me find (or explain the impossibility of finding) IDTFT$$\left[X[e^{j\omega}]\right]$$ for...

$$X\left[e^{j\omega}\right] = \left(\frac{1 - xx^{u - l}}{1 - x}\right)^v$$

If you conclude $$\nexists$$ IDTFT$$\left[X[e^{j\omega}]\right]$$, & you have good reason, would you also describe the family of GFs for which this method will not work?

### UPDATE 1

After realizing that the coefficients resulting from the expansion step are given by pascal's triangle, I was able to derive...

$$card\left(C\right) = \left[x^{n - vl}\right]\left(\frac{1 - xx^{u - l}}{1 - x}\right)^v\\ = \sum_{k = 0}^{v}\left[(-1)^k\left(\begin{array}{c}v\\k\end{array}\right) \left(\begin{array}{c}n + v - k(u - l + 1) - l\\n\end{array}\right)u[n - k(u - l + 1)] \right]$$

But can it be further simplified?