自然数nに対して[n] ={i∈N|1≤i≤n}とする。
$[n] = \{i \in \nats\ | 1 \leq i \leq n\}$
自然数nに対して,P(n)を?尿⊆[n]?韮⊆[n]|A∪B| = 3n4^(n−1)とする。
$\sum_{A\subseteq [n]} \sum_{B\subseteq [n]} \|A \cup B| = 3n4^{n-1}$
全ての自然数nに対してP(n)であることを帰納法で証明したいのですが、P(n)と仮定した後、どうすればP(n+1)になるかが全く分かりません。
nより小さい全ての自然数kに対してP(k)と仮定する方法も試しましたが、結局3n4^(n−1)がどう出来るのかが分かりません。
自然数は0を含みます。よろしくお願いします。
|
No.73226 - 2021/03/08(Mon) 11:40:51
| ☆ Re: 数学的帰納法 / IT | | | 数式編集ソフトで編集されたもののソースをそのまま貼り付けておられるようですが、意味不明です。
入力しなおされるか、画像で貼り付けられる必要があると思います。
|
No.73236 - 2021/03/08(Mon) 18:42:20 |
| ☆ Re: 数学的帰納法 / 黄桃 | | | #TeX表記は不要だと思いますが、分かりやすく書いてほしいですね。
まず、P(1)を使ってP(2)を計算してみます。
[1]={1},[2]={1,2}
[1]のすべての部分集合 φ,{1}
[2]のすべての部分集合 φ,{1},{2}=φ∪{2},{1,2}={1}∪{2}
P(2)=?農(A⊆[2]) ?農(B⊆[2])|A∪B|
=?農(A⊆[2], Aは2を含まない) ?農(B⊆[2], Bは2を含まない)|A∪B|
+?農(A⊆[2], Aは2を含む) ?農(B⊆[2], Bは2を含まない)|A∪B|
+?農(A⊆[2], Aは2を含まない) ?農(B⊆[2], Bは2を含む)|A∪B|
+?農(A⊆[2], Aは2を含む) ?農(B⊆[2], Bは2を含む)|A∪B|
=Σ_(A=φ,{1})Σ_(B=φ,{1})|A∪B|
+Σ_(A={2},{1,2})Σ_(B=φ,{1})|A∪B|
+Σ_(A=φ,{1})Σ_(B={1},{1,2})|A∪B|
+Σ_(A={1},{1,2})Σ_(B={1},{1,2})|A∪B|
=Σ_(A=φ,{1})Σ_(B=φ,{1})|A∪B|
+Σ_(A=φ,{1})Σ_(B=φ,{1})|A∪{2}∪B|
+Σ_(A=φ,{1})Σ_(B=φ,{1})|A∪B∪{2}|
+Σ_(A=φ,{1})Σ_(B=φ,{1})|A∪{2}∪B∪{2}|
=Σ_(A=φ,{1})Σ_(B=φ,{1})|A∪B|
+Σ_(A=φ,{1})Σ_(B=φ,{1})|A∪B|+1
+Σ_(A=φ,{1})Σ_(B=φ,{1})|A∪B|+1
+Σ_(A=φ,{1})Σ_(B=φ,{1})|A∪B|+1
=P(1)
+P(1)+#[1]*#[1]
+P(1)+#[1]*#[1]
+P(1)+#[1]*#[1]
=4P(1)+3*2*2
(#X=|X|=集合Xの要素数 |[x]|では紛らわしいので記号を変えてました)
同様に、
P(n)=?農(A⊆[n]) ?農(B⊆[n])|A∪B|
=P(n-1)
+P(n-1)+#[n-1]*#[n-1]
+P(n-1)+#[n-1]*#[n-1]
+P(n-1)+#[n-1]*#[n-1]
=4P(n-1)+3*(#[n-1])^2
=4P(n-1)+3*(2^(n-1))^2
がいえます。
|
No.73237 - 2021/03/08(Mon) 19:11:18 |
|
