数列の問題

方針：$\max \{i,j\}$ の値ごとに項をまとめる。

$1\leqq i\leqq n$, $1\leqq j\leqq n$ の $n^2$ 組 $(i,j)$ を、次の 3 種類に分ける。

(1) $i=j$ のとき

$i=j=k$ とすると、項は $k\cdot 2^k$ である。この部分の和は $\sum _{k=1}^{n}k\cdot 2^k$。

(2) $i<j$ のとき

$\min \{i,j\}=i$, $\max \{i,j\}=j$ なので、項は $i\cdot 2^j$ である。$j=k$ $(2\leqq k\leqq n)$ を固定して $i=1,2,\dots ,k-1$ について加えると
$$\sum _{i=1}^{k-1}i\cdot 2^k=\frac{(k-1)k}{2}\cdot 2^k.$$
これは $k=1$ のとき $0$ になるので、$k=1$ から加えてもよい。よってこの部分の和は $\sum _{k=1}^n\frac{k(k-1)}{2}\cdot 2^k$。

(3) $i>j$ のとき

$i$ と $j$ の役割を入れかえれば (2) と同じなので、和は (2) と等しい。

以上を合計すると
$$S_n=\sum _{k=1}^n\left\{k+2\cdot \frac{k(k-1)}{2}\right\}{2}^k=\sum _{k=1}^n{k}^2\cdot 2^k.$$

準備：$U_n=\sum _{k=1}^{n}k\cdot 2^k$ を求める。

$$2U_n-U_n=\sum _{k=2}^{n+1}(k-1)2^k-\sum _{k=1}^{n}k\cdot 2^k=n\cdot 2^{n+1}-\sum _{k=1}^n{2}^k.$$
ここで $\sum _{k=1}^n{2}^k=2^{n+1}-2$ なので
$$U_n=n\cdot 2^{n+1}-(2^{n+1}-2)=(n-1)2^{n+1}+2.$$

$T_n=\sum _{k=1}^n{k}^2\cdot 2^k$ を求める。

$$2T_n=\sum _{k=1}^n{k}^2\cdot 2^{k+1}=\sum _{k=2}^{n+1}(k-1{)}^2\cdot 2^k$$
であるから
$$T_n=2T_n-T_n=n^2\cdot 2^{n+1}+\sum _{k=2}^n\{(k-1{)}^2-k^2\}{2}^k-1^2\cdot 2^1.$$
$(k-1{)}^2-k^2=-(2k-1)$ であり、この式は $k=1$ のとき $-1$ になる。よって $k=1$ の項 $-1\cdot 2^1=-2$ を足して引けば
$$\sum _{k=2}^n\{(k-1{)}^2-k^2\}{2}^k=-\sum _{k=1}^n(2k-1)2^k+2$$
となり、
$$T_n=n^2\cdot 2^{n+1}-\sum _{k=1}^n(2k-1)2^k+2-2=n^2\cdot 2^{n+1}-\sum _{k=1}^n(2k-1)2^k.$$
さらに
$$\sum _{k=1}^n(2k-1)2^k=2U_n-(2^{n+1}-2)=2(n-1)2^{n+1}+4-2^{n+1}+2=(2n-3)2^{n+1}+6.$$
したがって
$$T_n=n^2\cdot 2^{n+1}-(2n-3)2^{n+1}-6=(n^2-2n+3)\cdot 2^{n+1}-6.$$

検算

• $n=1$ のとき：直接計算すると $1\cdot 2^1=2$、式の値は $2\cdot 4-6=2$。
• $n=2$ のとき：直接計算すると $2+4+4+8=18$、式の値は $3\cdot 8-6=18$。

いずれも一致する。

以上より
$$S_n=(n^2-2n+3)\cdot 2^{n+1}-6.$$

$\min \{i,j\}\cdot 2^{\max \{i,j\}}$ は $i,j$ について対称である。$i=j$ の項と $i\ne j$ の項に分けて数える。

対角項の和は ${\sum }_{k=1}^{n}k{2}^k$。

$j<i$ の項は、$i$ を固定すると ${\sum }_{j=1}^{i-1}j\cdot 2^i=\frac{i(i-1)}{2}{2}^i$。$i<j$ の項も同じ値になるので、非対角項の合計は $2{\sum }_{i=1}^n\frac{i(i-1)}{2}{2}^i={\sum }_{i=1}^{n}i(i-1)2^i$。

よって $S_n={\sum }_{k=1}^n\{k+k(k-1)\}{2}^k={\sum }_{k=1}^n{k}^2{2}^k$。

次に $T_n={\sum }_{k=1}^n{k}^2{2}^k$ を求める。$f(k)=(k^2-2k+3)2^{k+1}$ とおくと
$f(k)-f(k-1)=(k^2-2k+3)2^{k+1}-((k-1{)}^2-2(k-1)+3)2^k$
$=2^k\{2k^2-4k+6-(k^2-4k+6)\}=k^2{2}^k$。

したがって $T_n=f(n)-f(0)=(n^2-2n+3)2^{n+1}-3\cdot 2=(n^2-2n+3)2^{n+1}-6$。

検算：
- $n=1$ のとき、公式は $2\cdot 4-6=2$。直接計算も $1\cdot 2=2$ で一致。
- $n=2$ のとき、公式は $3\cdot 8-6=18$。直接計算は $2+4+4+8=18$ で一致。
- $n=3$ のとき、公式は $6\cdot 16-6=90$。$\sum k^2{2}^k=2+16+72=90$ で一致。

答え：$S_n=(n^2-2n+3)2^{n+1}-6$