4 (See the solution/explanation page)

Let $n$, $k$ be integers satisfying $1 \leq k \leq n$. From the $n$ integers $2^m$ ($m = 0, 1, 2, \cdots, n-1$), choose $k$ distinct elements and take their product. Let $a_{n,k}$ denote the sum of the ${}_{n}C_{k}$ integers obtained by taking such products over all possible ways of choosing $k$ integers. For example,
$$a_{4,3} = 2^0 \cdot 2^1 \cdot 2^2 + 2^0 \cdot 2^1 \cdot 2^3 + 2^0 \cdot 2^2 \cdot 2^3 + 2^1 \cdot 2^2 \cdot 2^3 = 120$$

(1) For integers $n \geq 2$, find $a_{n,2}$.

(2) For integers $n \geq 1$, consider the polynomial in $x$: $$f_n(x) = 1 + a_{n,1}x + a_{n,2}x^2 + \cdots + a_{n,n}x^n$$ Express $\dfrac{f_{n+1}(x)}{f_n(x)}$ and $\dfrac{f_{n+1}(x)}{f_n(2x)}$ as polynomials in $x$.

(3) Express $\dfrac{a_{n+1,k+1}}{a_{n,k}}$ in terms of $n$ and $k$.
%% Page 5