【解答・解説】2026年 早稲田大学 理工学部 数学 第4問

(1)　与えられた漸化式

$$a(2n)=3a(n)+1,\quad a(2n+1)=3a(n)+2\quad(n=1,2,\cdots)$$

および初期条件 $a(1)=2$ に従い，順次値を求める。

まず，$a(7)$ を求める。$7=2\cdot3+1$ であるから，

$$a(7)=a(2\cdot3+1)=3a(3)+2$$

ここで $a(3)$ は，$3=2\cdot1+1$ より

$$a(3)=a(2\cdot1+1)=3a(1)+2=3(2)+2=8$$

したがって，

$$a(7)=3(8)+2=26$$

次に，$a(9)$ を求める。$9=2\cdot4+1$ であるから，

$$a(9)=a(2\cdot4+1)=3a(4)+2$$

ここで $a(4)$ は，$4=2\cdot2$ より

$$a(4)=a(2\cdot2)=3a(2)+1$$

さらに $a(2)$ は，$2=2\cdot1$ より

$$a(2)=a(2\cdot1)=3a(1)+1=3(2)+1=7$$

よって，

$$a(4)=3(7)+1=22$$

したがって，

$$a(9)=3(22)+2=66+2=68$$

(2)　$a(2^n+1)$ の値を $n$ を用いて表すことを考える。漸化式より，奇数の項については

$$a(2m+1)=3a(m)+2$$

が成り立つ。ここで $m=2^{n-1}$ とおくと，$2m+1=2\cdot2^{n-1}+1=2^n+1$ となるので，

$$a(2^n+1)=3a(2^{n-1})+2\quad(n\geqq1)$$

となる。次に，$a(2^{n-1})$ について考える。$2^{n-1}$ は偶数であるから，漸化式の偶数の項の規則

$$a(2k)=3a(k)+1$$

を繰り返し適用できる。

$$\begin{aligned} a(2^{n-1})&=a(2\cdot2^{n-2})=3a(2^{n-2})+1\\ a(2^{n-2})&=3a(2^{n-3})+1\\ &\ \vdots\\ a(2^1)&=3a(1)+1 \end{aligned}$$

これらを $a(2^n+1)=3a(2^{n-1})+2$ に順次代入していく。

$$\begin{aligned} a(2^n+1)&=3a(2^{n-1})+2\\ &=3(3a(2^{n-2})+1)+2=3^2a(2^{n-2})+3\cdot1+2\\ &=3^2(3a(2^{n-3})+1)+3+2=3^3a(2^{n-3})+3^2+3+2\\ &\ \vdots\\ &=3^{n-1}a(2^1)+(3^{n-2}+\cdots+3^1)+2\\ &=3^{n-1}(3a(1)+1)+\sum_{k=1}^{n-2}3^k+2\\ &=3^na(1)+3^{n-1}+\sum_{k=1}^{n-2}3^k+2\\ &=2\cdot3^n+\sum_{k=1}^{n-1}3^k+2 \end{aligned}$$

ここで，最後の項2は $2\cdot3^0$ とみなせる。よって，

$$a(2^n+1)=2\cdot3^n+\sum_{k=1}^{n-1}1\cdot3^k+2\cdot3^0$$

これを $\displaystyle\sum_{k=0}^{n}b_k\cdot3^k$ の形と比較すると，係数 $b_k$ は以下のようになる。

• $k=n$ のとき，$b_n=2$
• $1\leqq k\leqq n-1$ のとき，$b_k=1$
• $k=0$ のとき，$b_0=2$

なお，$n=1$ のときは $a(2^1+1)=a(3)=8=2\cdot3^1+2\cdot3^0$ となり，中間項 $(1\leqq k\leqq n-1)$ は存在しないが，上記の規則 $(b_1=2,b_0=2)$ と矛盾しない。

(3)　求める和を $S_n=\displaystyle\sum_{k=1}^{2^n-1}a(k)$ とおく。自然数 $k$ の2進数表記の桁数に着目し，群に分けて和を計算する。第 $j$ 群を $2^{j-1}\leqq k\leqq2^j-1$ を満たす自然数 $k$ の集合とし，その和を $T_j$ とする。

$$T_j=\sum_{k=2^{j-1}}^{2^j-1}a(k)$$

このとき，求める和 $S_n$ は

$$S_n=\sum_{j=1}^{n}T_j$$

である。

まず $T_1$ を求める。範囲は $2^0\leqq k\leqq2^1-1$ 即ち $k=1$ のみである。

$$T_1=a(1)=2$$

次に $j\geqq2$ のとき，$T_j$ の漸化式を導く。区間 $[2^{j-1},2^j-1]$ に含まれる整数 $k$ は，$2m$ または $2m+1$（ただし $2^{j-2}\leqq m\leqq2^{j-1}-1$）の形で表せる。よって，

$$\begin{aligned} T_j&=\sum_{m=2^{j-2}}^{2^{j-1}-1}(a(2m)+a(2m+1))\\ &=\sum_{m=2^{j-2}}^{2^{j-1}-1}((3a(m)+1)+(3a(m)+2))\\ &=\sum_{m=2^{j-2}}^{2^{j-1}-1}(6a(m)+3)\\ &=6\sum_{m=2^{j-2}}^{2^{j-1}-1}a(m)+\sum_{m=2^{j-2}}^{2^{j-1}-1}3 \end{aligned}$$

右辺のシグマの中身 $\displaystyle\sum a(m)$ は，定義より $T_{j-1}$ そのものである。また，定数3を足す回数（項数）は $(2^{j-1}-1)-2^{j-2}+1=2^{j-2}$ である。したがって，次の漸化式が得られる。

$$T_j=6T_{j-1}+3\cdot2^{j-2}\quad(j\geqq2)$$

この漸化式を解く。両辺を $2^j$ で割ると，

$$\frac{T_j}{2^j}=3\frac{T_{j-1}}{2^{j-1}}+\frac34$$

数列 $\left\{\frac{T_j}{2^j}\right\}$ は，初項 $\frac{T_1}{2^1}=\frac22=1$，公比3の等比数列の形に近い。特性方程式 $c=3c+\frac34$ を解くと $c=-\frac38$ となるので

$$\frac{T_j}{2^j}+\frac38=3\left(\frac{T_{j-1}}{2^{j-1}}+\frac38\right)$$

よって，

$$\frac{T_j}{2^j}+\frac38=\left(1+\frac38\right)\cdot3^{j-1}=\frac{11}{8}\cdot3^{j-1}$$ $$\frac{T_j}{2^j}=\frac{11}{8}\cdot3^{j-1}-\frac38$$ $$T_j=\frac{11}{8}\cdot3^{j-1}\cdot2^j-\frac38\cdot2^j=\frac{11}{4}\cdot6^{j-1}-\frac38\cdot2^j$$

これは $j=1$ のとき $T_1=\frac{11}{4}-\frac34=2$ となり成立する。

最後に総和 $S_n$ を計算する。

$$\begin{aligned} S_n&=\sum_{j=1}^{n}T_j=\sum_{j=1}^{n}\left(\frac{11}{24}\cdot6^j-\frac38\cdot2^j\right)\\ &=\frac{11}{24}\sum_{j=1}^{n}6^j-\frac38\sum_{j=1}^{n}2^j\\ &=\frac{11}{24}\cdot\frac{6(6^n-1)}{6-1}-\frac38\cdot\frac{2(2^n-1)}{2-1}\\ &=\frac{11}{20}(6^n-1)-\frac34(2^n-1)\\ &=\frac{11(6^n-1)-15(2^n-1)}{20}\\ &=\frac{11\cdot6^n-11-15\cdot2^n+15}{20}\\ &=\frac{11\cdot6^n-15\cdot2^n+4}{20} \end{aligned}$$

補足

(3) の考え方を視覚的に理解するために，数列 $a(k)$ の生成規則を木構造で表すと以下のようになります。各深さにあるノードの総和が $T_j$ に対応します。

図のように，深さ $j$ の層には $2^{j-1}$ 個の項があり，それぞれの項 $a(m)$ から次の層の $a(2m),a(2m+1)$ が生成されます。この親子関係における和の変化（$a(2m)+a(2m+1)=6a(m)+3$）を利用することで，層ごとの和 $T_j$ の漸化式を立てることができます。