Finding a General Pattern for the Partial fraction of $\frac{1}{{{\left( 1+x \right)}^{n}}\left( 1+{{x}^{2}} \right)}$

Lemma. For $|x+1| < \sqrt{2}$, we have $$ \begin{gathered} \sum_{k=0}^{\infty} \cos(k\pi/4)\left(\frac{x+1}{\sqrt{2}}\right)^k = \frac{1-x}{1+x^2}, \\ \sum_{k=0}^{\infty} \sin(k\pi/4)\left(\frac{x+1}{\sqrt{2}}\right)^k = \frac{1+x}{1+x^2}. \end{gathered}$$

In particular, using $\cos(x) + \sin(x) = \sqrt{2}\sin(x+\frac{\pi}{4})$, we obtain

$$ \sum_{k=0}^{\infty} \frac{\sin((k+1)\pi/4)}{2^{(k+1)/2}} (x+1)^k = \frac{1}{1+x^2} $$

for $|x+1| < \sqrt{2}$. Plugging this to OP's rational function,

$$ \frac{1}{(1+x)^n(1+x^2)} = \left( \sum_{k=1}^{n} \frac{\sin(k\pi/4)}{2^{k/2}} \frac{1}{(x+1)^{n+1-k}} \right) + \sum_{k=0}^{\infty} \frac{\sin((n+k+1)\pi/4)}{2^{(n+k+1)/2}} (x+1)^k. $$

The latter sum can be further simplified by using the addition formula for $\sin$, yielding

\begin{align*} \sum_{k=0}^{\infty} \frac{\sin((n+k+1)\pi/4)}{2^{(n+k+1)/2}} (x+1)^k &= \frac{\sin((n+1)\pi/4)}{2^{(n+1)/2}} \frac{1-x}{1+x^2} + \frac{\cos((n+1)\pi/4)}{2^{(n+1)/2}} \frac{1+x}{1+x^2} \\ &= \frac{\cos(n\pi/4)}{2^{n/2}} \frac{1}{1+x^2} - \frac{\sin(n\pi/4)}{2^{n/2}} \frac{x}{1+x^2} \end{align*}

Combining altogether, we get

$$ \frac{1}{(1+x)^n(1+x^2)} = \left( \sum_{k=1}^{n} \frac{\sin(k\pi/4)}{2^{k/2}} \frac{1}{(x+1)^{n+1-k}} \right) + \frac{\cos(n\pi/4)-x \sin(n\pi/4)}{2^{n/2}(1+x^2)}. $$

Although this is shown initially on the region $|x+1| < \sqrt{2}$, this continues to hold everywhere since any two rational functions which coincide at infinitely many points must be equal.

Put \begin{equation*} f(x)=\dfrac{1}{(1+x)^n(1+x^2)}. \end{equation*} Then the partial fraction of $f(x)$ has the form \begin{equation*} f(x) =\dfrac{ax+b}{1+x^2} + \sum_{k=1}^{n}\dfrac{c_k}{(1+x)^{n+1-k}}\tag {1} \end{equation*} or \begin{equation*} f(x) = \dfrac{d_1}{x+i}+\dfrac{d_2}{x-i}+\sum_{k=1}^{n}\dfrac{c_k}{(1+x)^{n+1-k}} \end{equation*} where \begin{gather*} d_1= \underset{x=-i}{\rm{res}}f(x) = \dfrac{1}{(1-i)^n(-2i)}=-\dfrac{e^{i\frac{n\pi}{4}}}{\sqrt{2}^{n}2i}\\[2ex] d_2= \underset{x=i}{\rm{res}}f(x) = \dfrac{1}{(1+i)^n(2i)}=\dfrac{e^{-i\frac{n\pi}{4}}}{\sqrt{2}^{n}2i}. \end{gather*} However, \begin{gather*} a=d_1+d_2 =-\dfrac{\sin\left(\frac{n\pi}{4}\right)}{2^{\frac{n}{2}}}\\[2ex] b=i(d_2-d_1)= \dfrac{\cos\left(\frac{n\pi}{4}\right)}{2^{\frac{n}{2}}}. \end{gather*} Furthermore \begin{gather*} c_k = \underset{x=-1}{\rm{res}}(1+x)^{n-k}f(x)= \underset{x=-1}{\rm{res}}\dfrac{1}{(1+x)^k(1+x^2)}=\\[2ex] \left.\dfrac{1}{(k-1)!}\dfrac{d^{k-1}}{dx^{k-1}}\left(\dfrac{1}{2i}\left(\dfrac{1}{x-i}-\dfrac{1}{x+i}\right)\right)\right|_{x=-1} =\\[2ex] \dfrac{1}{2i(k-1)!}(-1)^{k-1}(k-1)!\left(\dfrac{1}{(-1-i)^{k}}-\dfrac{1}{(-1+i)^{k}}\right)= \dfrac{1}{2i}\left(\dfrac{1}{(1-i)^{k}}-\dfrac{1}{(1+i)^{k}}\right)=\\[2ex] \dfrac{1}{2i}\left(\dfrac{e^{i\frac{k\pi}{4}}}{\sqrt{2}^{k}}-\dfrac{e^{-i\frac{k\pi}{4}}}{\sqrt{2}^{k}}\right) = \dfrac{\sin\left(\frac{k\pi}{4}\right)}{2^{\frac{k}{2}}} \end{gather*} Now we know all coefficients in (1).

I'm going to carry this almost all the way through and stop just before the final step because I got tired of all the necessary details.

$\begin{array}\\ f_n(x) &=\frac{1}{{{\left( 1+x \right)}^{n}}\left( 1+{{x}^{2}} \right)}\\ &=\frac{a+bx}{1+x^2}+\sum_{k=1}^n \frac{c_k}{(1+x)^k}\\ g_n(x) &=f_n(x)(1+x^2)(1+x)^n\\ &=1\\ &=(a+bx)(1+x)^n+\sum_{k=1}^n c_k(1+x^2)(1+x)^{n-k}\\ g_n(-1) &=2c_n\\ c_n &=\frac12\\ g_n(i) &=1\\ &=(a+bi)(1+i)^n\\ &=2^{n/2}(a+bi)(\frac{1+i}{\sqrt{2}})^n\\ &=2^{n/2}(a+bi)(e^{i\pi/4})^n\\ &=2^{n/2}(a+bi)e^{ni\pi/4}\\ a+bi &=2^{-n/2}e^{-ni\pi/4}\\ &=2^{-n/2}(\cos(-n\pi/4)+i\sin(-n\pi/4))\\ &=2^{-n/2}(1, \frac{1-i}{\sqrt{2}}, -i, -\frac{1+i}{\sqrt{2}}, -1, -\frac{1-i}{\sqrt{2}}, i, \frac{1+i}{\sqrt{2}}) \quad\text{for }n\equiv (0,1,2,3,4,5,6,7)\bmod 8 \\ &=(\frac1{2^{n/2}}, \frac{1-i}{2^{(n+1)/2}}, -\frac{i}{2^{n/2}}, -\frac{1+i}{2^{(n+1)/2}}, -\frac1{2^{n/2}}, -\frac{1-i}{2^{(n+1)/2}}, \frac{i}{2^{n/2}}, \frac{1+i}{2^{(n+1)/2}})\\ &=(\frac1{2^{4m}}, \frac{1-i}{2^{4m+1}}, -\frac{i}{2^{4m+1}}, -\frac{1+i}{2^{4m+2}}, -\frac1{2^{4m+2}}, -\frac{1-i}{2^{4m+3}}, \frac{i}{2^{4m+3}}, \frac{1+i}{2^{4m+4}}) \quad n=8m+k, k=0...7\\ &=(\frac1{2^{4m}}, \frac{1-i}{2^{4m+1}}, \frac{-i}{2^{4m+1}}, \frac{-1-i}{2^{4m+2}}, \frac{-1}{2^{4m+2}}, \frac{-1+i}{2^{4m+3}}, \frac{i}{2^{4m+3}}, \frac{1+i}{2^{4m+4}})\\ &=\dfrac1{2^{\lceil n/2 \rceil}}(1, 1-i, -i, -1-i, -1, -1+i, i, 1+i)\\ g_n^{(j)}(x) &=0 \qquad\text{for } j \ge 1\\ &=((a+bx)(1+x)^n)^{(j)}+\sum_{k=1}^n c_k((1+x^2)(1+x)^{n-k})^{(j)}\\ &=u^{(j)}(x)+\sum_{k=1}^n c_kv_k^{(j)}(x)\\ u^{(j)}(x) &=((a+bx)(1+x)^n)^{(j)}\\ &=\sum_{h=0}^j \binom{j}{h}(a+bx)^{(h)}(1+x)^n)^{(j-h)}\\ (a+bx)^{(h)} &=a+bx, b, 0, ... \qquad\text{for }h = 0, 1, 2, ...\\ ((1+x)^n)^{(h)} &=\frac{n!}{(n-h)!}(1+x)^{n-h}\\ v_k^{(j)}(x) &=((1+x^2)(1+x)^{n-k})^{(j)}(x)\\ &=\sum_{h=0}^j \binom{j}{h}(1+x^2)^{(h)}((1+x)^{n-k})^{(j-h)}(x)\\ (1+x^2)^{(h)} &=1+x^2, 2x, 2, 0, ... \qquad \text{for } h=0, 1, 2, ...\\ ((1+x)^{n-k})^{(h)}(x) &=\frac{(n-k)!}{(n-k-h)!}(1+x)^{n-k-h}\\ \end{array} $

And at this point, I'll stop.