式と証明 ★★★ 応用の問題 全8問

方針

解答

⓪ 発想(どう考え始めるか) 二項係数の和は、$(1+x{)}^n$ の展開式に値を代入するとすぐに出る。

$x=1$ を入れれば全部の和が $2^n$、$x=-1$ を入れれば符号が交代して和が $0$。証明したい和が既知の展開式のどの代入で現れるか。それを逆算するのが発想の核だ。

(1) $x=1$ を代入すると、左辺 $(1+1{)}^n=2^n$、右辺 $\sum _{k=0}^n{}_n{\mathrm{C}}_k\cdot 1^k=\sum {}_n{\mathrm{C}}_k$。よって

$${}_n{\mathrm{C}}_0+{}_n{\mathrm{C}}_1+\cdots +{}_n{\mathrm{C}}_n=2^n$$

(2) $x=-1$ を代入すると、左辺 $(1-1{)}^n=0$、右辺 $\sum _{k=0}^n{}_n{\mathrm{C}}_k(-1{)}^k$。よって

$${}_n{\mathrm{C}}_0-{}_n{\mathrm{C}}_1+\cdots +(-1{)}^n{}_n{\mathrm{C}}_n=0$$

$■$

((1)と(2)を足し引きすると、偶数番目の二項係数の和と奇数番目の和がともに $2^{n-1}$ になることも導ける。)

発展。 代入する値を変えるだけで、別の和が次々に生まれる。

$x=2$ を入れれば ${\sum }_{k=0}^n{}_n{\mathrm{C}}_k{2}^k=3^n$、一般に $x=t$ で ${\sum }_{k=0}^n{}_n{\mathrm{C}}_k{t}^k=(1+t{)}^n$。重み $t^k$ の付いた二項係数の和が、$t$ を選ぶだけで手に入る。

さらに $x$ に $1$ の虚数乗根を代入すると、番号がとびとびの二項係数だけを集めた和も取り出せる。$1$ の $m$ 乗根をすべて代入して平均をとると、$m$ 個おきの二項係数の和が残る(1の冪根フィルター)。$(1+x{)}^n$ という $1$ 本の恒等式が代入値しだいで無数の和を生む母関数である。

別解

別解:部分集合を数えて示す(苦手な人向けの数え上げルート)。 代入を使わず、集合の要素の選び方で考える。

$n$ 個のものからいくつか選ぶ選び方は、各要素を「選ぶ・選ばない」の $2$ 通りだから全部で $2^n$ 通り。一方、ちょうど $k$ 個選ぶ選び方は ${}_n{\mathrm{C}}_k$ 通り。$k=0,1,\dots ,n$ で足し合わせれば同じ全体を数えたことになり、$(1)$ が言える。

$(2)$ は「偶数個選ぶ」場合と「奇数個選ぶ」場合が同数であることを示せばよい。要素を $1$ つ決め、それを「入れる・入れない」で切り替えると、偶数個の選び方と奇数個の選び方が過不足なく $1$ 対 $1$ に対応する($n\ge 1$)。だから両者は同数で、差をとった交代和は $0$。

代入(本解)と同じ結論だが、二項係数が「選び方の個数」だという原点に戻ると、等式の意味が見える。本解と同じ答えだ。

方針

解答

⓪ 発想(どう考え始めるか) ${}_4{\mathrm{C}}_k\cdot {}_3{\mathrm{C}}_{3-k}$ の和は、直接計算しなくても係数比較で出せる。

同じ多項式 $(1+x{)}^7$ を、$(1+x{)}^4(1+x{)}^3$ と分けて書く。両辺で $x^3$ の係数を比べればよい。「同じ式を $2$ 通りに書き、特定の項の係数を照合する」。この係数比較は組合せ論的な恒等式を作るのに役立つ道具だ。

左辺 $(1+x{)}^4(1+x{)}^3$ で $x^3$ の項を作るには、$(1+x{)}^4$ から $x^k$($k=0,1,2,3$)、$(1+x{)}^3$ から $x^{3-k}$ を取り出してかける。その係数の積を足すと、$x^3$ の係数は

$$\sum _{k=0}^3{}_4{\mathrm{C}}_k{}_3{\mathrm{C}}_{3-k}$$

一方、右辺 $(1+x{)}^7$ の $x^3$ の係数は ${}_7{\mathrm{C}}_3$。左辺と右辺は同じ式だから、$x^3$ の係数も等しい。値は

$${}_7{\mathrm{C}}_3=\frac{7\cdot 6\cdot 5}{3\cdot 2\cdot 1}=35$$

(『同じ式を2通りに展開して係数を比べる』と、二項係数の等式が得られる。)

発展。 この等式はより一般の ${}_{m+n}{\mathrm{C}}_r={\sum }_k{}_m{\mathrm{C}}_k{}_n{\mathrm{C}}_{r-k}$(ヴァンデルモンドの畳み込み)の一例だ。

$(1+x{)}^m(1+x{)}^n=(1+x{)}^{m+n}$ の $x^r$ の係数を両辺で比べれば、同じ係数比較の論法でそのまま示せる。$m$、$n$、$r$ を自由に選べる分だけ、作れる恒等式の幅が広がる。

見方を変えると、多項式の積の係数は、$2$ つの係数列を『ずらしながら掛けて足す』畳み込みになっている。数列を多項式の係数に載せる母関数の立場では、積がいつでも畳み込みに対応する。和の恒等式を量産する源が、この一点にある。

別解

別解:委員の選び方として数える(苦手な人向けの数え上げルート)。 式変形でなく、具体的な選び方で両辺を読む。

男子 $4$ 人・女子 $3$ 人の合わせて $7$ 人から $3$ 人の委員を選ぶ。総数は右辺の ${}_7{\mathrm{C}}_3$ 通りだ。同じ選び方を「男子を $k$ 人選ぶ」で場合分けする。男子 $k$ 人の選び方は ${}_4{\mathrm{C}}_k$、残る女子 $3-k$ 人の選び方は ${}_3{\mathrm{C}}_{3-k}$、掛けて ${}_4{\mathrm{C}}_k{}_3{\mathrm{C}}_{3-k}$。$k=0,1,2,3$ で足せば左辺になる。

同じ人数の選び方を $2$ 通りに数えたから左辺 $=$ 右辺、値は ${}_7{\mathrm{C}}_3=35$。本解と同じ答えだ。

方針

解答

⓪ 発想(どう考え始めるか) 余りは $1$ 次以下だから $ax+b$ とおける。未知数は $2$ つある。

$x=1$ を代入すると式が立つが、これ $1$ 本では $a$、$b$ を決めきれない。足りない $1$ 本をどこから作るか。

割る式が重解 $(x-1{)}^2$ を持つことに注目する。両辺を微分してから $x=1$ を入れると、$(x-1{)}^2$ の項が消えて第 $2$ の式が出る。「重根で割った余りは、微分でもう $1$ 本条件を絞り出す」のが発想だ。

余りを $ax+b$ とおく。

$$x^5=(x-1{)}^{2}Q(x)+ax+b$$

$x=1$ を代入:$1=a+b$ … ①

$(x-1{)}^2$ は $x=1$ を重解に持つので、両辺を $x$ で微分してから $x=1$ を代入すると、右辺の $(x-1{)}^2$ を含む項が $x=1$ で消える。

$$5x^4=2(x-1)Q(x)+(x-1{)}^2{Q}^{\prime }(x)+a$$

$x=1$ を代入:$5=a$。①より $b=1-5=-4$。よって余りは

$$5x-4$$

(別解:$x=1+t$ とおくと $x^5=(1+t{)}^5=1+5t+10t^2+\cdots$。$(x-1{)}^2=t^2$ で割った余りは $t$ の1次まで、つまり $1+5t=1+5(x-1)=5x-4$。同じ答えだ。)

発展。 一般に、$f(x)$ を $(x-a{)}^2$ で割った余りは $f(a)+f^{\prime }(a)(x-a)$ になる。

これは点 $(a,f(a))$ での接線そのものだ。今回は $a=1$、$f(1)=1$、$f^{\prime }(1)=5$ で余り $5x-4=1+5(x-1)$、たしかに $x=1$ での接線に一致する。$(x-a{)}^m$ で割れば、余りはテイラー展開の初め $m$ 項になる。関数を多項式で近似する補間(エルミート補間)の基礎がここにある。

別解

別解:素直に割り算する(苦手な人向けの愚直ルート)。 技を使わず、$x^5$ を $x^2-2x+1$($=(x-1{)}^2$)でそのまま割る。

割り算を進めると商は $x^3+2x^2+3x+4$、そして最後に余り $5x-4$ が残る。

$$x^5=(x^2-2x+1)(x^3+2x^2+3x+4)+(5x-4).$$

商を掛けて余りを足すと $x^5$ に戻ることを確かめれば確実だ。微分や置きかえの工夫がなくても、割り算そのものを実行すれば余り $5x-4$ にたどり着く。本解と同じ答えだ。

方針

解答

⓪ 発想(どう考え始めるか) $(1)$ で部分分数の形を用意し、$(2)$ でそれを和に代入する。

すると隣どうしが打ち消し合い、両端だけが残る。いわゆる望遠鏡和だ。「バラして、隣接項を相殺させ、両端だけ残す」。これが和の計算の定跡で、$(1)$ は $(2)$ のための道具立てだと見抜く。

(1) 右辺の $\frac{1}{k(k+1)}-\frac{1}{(k+1)(k+2)}$ を、共通因数 $\frac{1}{k+1}$ でくくる。

$$\frac{1}{k+1}\left(\frac{1}{k}-\frac{1}{k+2}\right)=\frac{1}{k+1}\cdot \frac{(k+2)-k}{k(k+2)}=\frac{1}{k+1}\cdot \frac{2}{k(k+2)}=\frac{2}{k(k+1)(k+2)}$$

これを $\frac{1}{2}$ 倍すると $\frac{1}{k(k+1)(k+2)}$。確かに成り立つ。

(2) (1)より

$$\sum _{k=1}^n\frac{1}{k(k+1)(k+2)}=\frac{1}{2}\sum _{k=1}^n\left(\frac{1}{k(k+1)}-\frac{1}{(k+1)(k+2)}\right)$$

中身は隣の項どうしが打ち消し合う(望遠鏡和)。$k=1$ の $\frac{1}{1\cdot 2}$ と、$k=n$ の $-\frac{1}{(n+1)(n+2)}$ だけが残る。

$$=\frac{1}{2}\left(\frac{1}{2}-\frac{1}{(n+1)(n+2)}\right)=\frac{1}{4}-\frac{1}{2(n+1)(n+2)}$$

通分して整理する。

$$=\frac{(n+1)(n+2)-2}{4(n+1)(n+2)}=\frac{n^2+3n}{4(n+1)(n+2)}=\frac{n(n+3)}{4(n+1)(n+2)}$$

発展。 同じ手はより長い積 $\frac{1}{k(k+1)\cdots (k+m)}$ にも使える。

一般に $\frac{1}{k(k+1)\cdots (k+m)}=\frac{1}{m}\left(\frac{1}{k(k+1)\cdots (k+m-1)}-\frac{1}{(k+1)\cdots (k+m)}\right)$ と、隣接項の差に書ける。だから和はいつでも望遠鏡和になり、両端だけが残る。隣り合う項の差で表して和を求めるこの操作は、積分の離散版にあたる差分法だ。$m=1$ なら ${\sum }_{k=1}^n\frac{1}{k(k+1)}=\frac{n}{n+1}$、$m=2$ が今回、と同じ枠組みで一般化できる。

別解

別解:答えを予想して、数学的帰納法で示す(得意な人向けの別論法)。 望遠鏡和を使わず、求める式 $S_n=\frac{n(n+3)}{4(n+1)(n+2)}$ を仮に置き、帰納法で確かめる。

$n=1$ では左辺 $\frac{1}{1\cdot 2\cdot 3}=\frac{1}{6}$、右辺 $\frac{1\cdot 4}{4\cdot 2\cdot 3}=\frac{1}{6}$ で一致する。$n$ で成り立つとして、次の項 $\frac{1}{(n+1)(n+2)(n+3)}$ を足す。通分すると分子は $n(n+3{)}^2+4$ で、これは $(n+1{)}^2(n+4)$ と因数分解できる。約分すると和は

$$S_n+\frac{1}{(n+1)(n+2)(n+3)}=\frac{(n+1)(n+4)}{4(n+2)(n+3)}$$

となり、$S_n$ の $n$ を $n+1$ に置きかえた形にちょうど等しい。よってすべての $n$ で成り立つ。相殺のしくみを追う本解に対し、帰納法は「予想した式を階段状に確定する」別の論理だ。本解と同じ答えだ。

方針

解答

⓪ 発想(どう考え始めるか) 左辺を展開すると、定数 $3$ と $\frac{a}{b}+\frac{b}{a}$ 型のペアが $3$ 組現れる。

各ペアは相加相乗で $2$ 以上と下から押さえられる。「展開して、相加相乗が使えるペアに分け、足し合わせる」。基本の $2$ 変数問題の発想を、$3$ 変数へ広げた総合問題だと見る。

左辺を展開する。

$$(a+b+c)\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right)=3+\left(\frac{a}{b}+\frac{b}{a}\right)+\left(\frac{b}{c}+\frac{c}{b}\right)+\left(\frac{c}{a}+\frac{a}{c}\right)$$

各ペアに相加相乗を使うと $\frac{a}{b}+\frac{b}{a}\ge 2$、$\frac{b}{c}+\frac{c}{b}\ge 2$、$\frac{c}{a}+\frac{a}{c}\ge 2$。よって

$$\ge 3+2+2+2=9$$

まとめ:等号はすべてのペアで成り立つとき、つまり $a=b=c$ のとき。$■$

発展。 この不等式は $n$ 変数に一般化できる。正の数 $a_1,\dots ,a_n$ で $(a_1+\cdots +a_n)\left(\frac{1}{a_1}+\cdots +\frac{1}{a_n}\right)\ge n^2$、等号は全部等しいときだ。

見方を変えると、これは相加平均が調和平均以上であること(AM $\ge$ HM)に等しい。実際 $\frac{a_1+\cdots +a_n}{n}\ge \frac{n}{\frac{1}{a_1}+\cdots +\frac{1}{a_n}}$ を移項すると上の形になる。「和」と「逆数の和」の積が、変数の個数の $2$ 乗で下から抑えられる。平均どうしの大小という、より一般の原理がここに現れている。

別解

別解:コーシー・シュワルツの不等式を使って一度に示す(得意な人向けの高い視点)。 展開せず、$2$ 乗和の積の不等式に乗せる。

$3$ つの数の組 $(\sqrt{a},\sqrt{b},\sqrt{c})$ と $\left(\frac{1}{\sqrt{a}},\frac{1}{\sqrt{b}},\frac{1}{\sqrt{c}}\right)$ にコーシー・シュワルツを使う。

$$(a+b+c)\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right)\ge {\left(\sqrt{a}\cdot \frac{1}{\sqrt{a}}+\sqrt{b}\cdot \frac{1}{\sqrt{b}}+\sqrt{c}\cdot \frac{1}{\sqrt{c}}\right)}^2=(1+1+1{)}^2=9.$$

各項の積がすべて $1$ になるのがしくみの要だ。等号はコーシー・シュワルツの等号、すなわち $2$ つの組が比例する $a=b=c$ のとき。展開して $3$ 組のペアに分ける本解と同じ答えに、$1$ 行で届く。

方針

解答

⓪ 発想(どう考え始めるか) コーシー・シュワルツ $(a^2+b^2)(x^2+y^2)\ge (ax+by{)}^2$ に、条件 $a^2+b^2=1$、$x^2+y^2=1$ を流し込む。

すると $(ax+by{)}^2\le 1$。あとは絶対値ではさめば $ax+by\le 1$ が出る。「証明済みの強い不等式に条件を代入する」。この道具の再利用が発想だ。

条件 $a^2+b^2=1$、$x^2+y^2=1$ を代入すると

$$1\times 1\ge (ax+by{)}^2\text{すなわち}(ax+by{)}^2\le 1$$

$2$ 乗が $1$ 以下なので $-1\le ax+by\le 1$。よって特に

$$ax+by\le 1$$

が成り立つ。$■$

(等号は $ay=bx$ かつ条件を満たすとき、つまり $(x,y)=(a,b)$ のとき成り立つ。)

発展。 $a^2+b^2=1$ を固定し、$ax+by$ を単位円上の点 $(x,y)$ の関数として最大化してみる。

最大は $(x,y)=(a,b)$ のときで、値は $1$。つまり「半径 $1$ の円上で $1$ 次式 $ax+by$ を最大化する」と、答えは係数ベクトルの長さ $\sqrt{a^2+b^2}=1$ に等しい。

一般に、半径 $r$ の円 $x^2+y^2=r^2$ 上での $ax+by$ の最大値は $r\sqrt{a^2+b^2}$。円や領域の上で $1$ 次式を最大化するのは線形計画法の考え方で、最大を与える境界の点が係数ベクトルの向きを表している。

別解

別解:角で表して、余弦に読みかえる(苦手な人向けの幾何ルート)。 $2$ 点は単位円上にあるから、角度で表せる。

$a=\cos \alpha$、$b=\sin \alpha$、$x=\cos \beta$、$y=\sin \beta$ とおく。すると

$$ax+by=\cos \alpha \cos \beta +\sin \alpha \sin \beta =\cos (\alpha -\beta ).$$

余弦は必ず $1$ 以下だから $ax+by=\cos (\alpha -\beta )\le 1$。等号は $\alpha =\beta$、すなわち $2$ 点が一致する $(x,y)=(a,b)$ のとき。$ax+by$ が「$2$ 点のなす角の余弦」だと見えるのがこのルートの利点で、図の $\theta$ がそのまま使える。本解と同じ答えだ。

方針

解答

⓪ 発想(どう考え始めるか) $x+2y=4$ という和が一定の条件のもとで、$xy$ を最大にしたい。

相加相乗は「和が一定なら、積は $2$ 数が等しいときに最大」と教える。ただし和が一定なのは $x$ と $2y$ のほう。積を $x\cdot 2y$ で組めば和が一定の $4$ に乗る。この「相加相乗が使える積の組み方」を工夫すれば解ける。

$x>0$、$2y>0$ に相加相乗を使う。$x+2y=4$ なので

$$4=x+2y\ge 2\sqrt{x\cdot 2y}=2\sqrt{2xy}$$

両辺を $2$ で割って $2\ge \sqrt{2xy}$、$2$ 乗して $4\ge 2xy$、つまり $xy\le 2$。等号は $x=2y$ のとき。これと $x+2y=4$ を連立すると $2y+2y=4$、$y=1$、$x=2$。よって $x=2$、$y=1$ のとき最大値 $2$。$■$

(『和が一定なら、相加相乗で積の最大がわかる』。$x$ と $2y$ をペアにするのがコツだ。)

発展。 「和が一定なら積は等しいとき最大、積が一定なら和は等しいとき最小」。相加相乗はこの $2$ つの向きをまとめて教える双対の関係だ。

同じことは図形にも現れる。周の長さが一定の長方形で面積が最大なのは正方形。周が固定($2$ 辺の和が一定)で面積($2$ 辺の積)を最大にする問題そのものだ。

今回は $x$ と $2y$ の和が一定で、$x=2y$ のとき積が最大になった。より一般に、$px+qy$ を一定に保って $x^a{y}^b$ を最大化する問題は、重み付きの相加相乗で解ける。

別解

別解:$1$ 変数に直して平方完成する(苦手な人向けの実感ルート)。 相加相乗を使わず、条件で文字を $1$ つ消す。

$x+2y=4$ より $x=4-2y$。これを代入すると

$$xy=(4-2y)y=4y-2y^2=-2(y-1{)}^2+2.$$

$-2(y-1{)}^2$ は $0$ 以下だから、$xy$ は $y=1$ のとき最大値 $2$。このとき $x=4-2=2$。定義域 $0<y<2$ の内側に頂点 $y=1$ があることも確かめておく。

放物線の頂点を読むだけなので、相加相乗を思いつかなくても最大値 $2$($x=2$、$y=1$)に届く。本解と同じ答えだ。

方針

解答

⓪ 発想(どう考え始めるか) 差 $a^2+b^2+c^2-(ab+bc+ca)$ を、$2$ 乗の和として書きたい。

そのまま見ても平方は見えない。全体を $2$ 倍すると、$(a-b{)}^2+(b-c{)}^2+(c-a{)}^2$ という $3$ つの $2$ 乗の和になる。「$2$ 倍して対称に $2$ 乗を組む」のが定跡だ。等号は $3$ つの $2$ 乗が同時に $0$、つまり $a=b=c$ のときと読める。

差を $2$ 倍して考える。

$$2\{a^2+b^2+c^2-(ab+bc+ca)\}=2a^2+2b^2+2c^2-2ab-2bc-2ca$$

これを $3$ 組に分ける。

$$=(a^2-2ab+b^2)+(b^2-2bc+c^2)+(c^2-2ca+a^2)=(a-b{)}^2+(b-c{)}^2+(c-a{)}^2$$

$2$ 乗の和なので $0$ 以上。よって差も $0$ 以上、つまり

$$a^2+b^2+c^2\ge ab+bc+ca$$

まとめ:等号は $(a-b{)}^2=(b-c{)}^2=(c-a{)}^2=0$、つまり $a=b=c$ のとき。$■$

発展。 この不等式は「散らばりは $0$ 以上」という事実と同じ内容だ。

$a$、$b$、$c$ の平均を $m$ とすると、$a^2+b^2+c^2-(ab+bc+ca)=\frac{3}{2}\{(a-m{)}^2+(b-m{)}^2+(c-m{)}^2\}$ と書ける。右辺は平均からのずれの $2$ 乗の和、つまり分散に比例する量で、必ず $0$ 以上。等号は散らばりが $0$、すなわち $a=b=c$。

$n$ 変数版は $(n-1)(a_1^2+\cdots +a_n^2)\ge 2{\sum }_{i<j}{a}_i{a}_j$ で、左辺 $-$ 右辺が ${\sum }_{i<j}(a_i-a_j{)}^2$ という平方の和になる。これは、差が半正定値な $2$ 次形式になっているということだ。

別解

別解:$a$ の $2$ 次式とみて、判別式で示す(得意な人向けの高い視点)。 不等式を $a$ についての $2$ 次不等式と見る。

左辺 $-$ 右辺を $a$ で整理すると

$$f(a)=a^2-(b+c)a+(b^2+c^2-bc).$$

$a^2$ の係数は $1>0$ で下に凸。判別式は

$$D=(b+c{)}^2-4(b^2+c^2-bc)=-3(b-c{)}^2\le 0.$$

判別式が $0$ 以下だから $f(a)$ は常に $0$ 以上、つまり $a^2+b^2+c^2\ge ab+bc+ca$。等号は $D=0$ かつ頂点、すなわち $b=c$ と $a=\frac{b+c}{2}=b$ が重なる $a=b=c$ のとき。$b$、$c$ を定数と見て $1$ 変数の $2$ 次関数に落とすと、判別式が符号を決めてくれる。本解と同じ結論だ。