Question Number 195079 by sonukgindia last updated on 23/Jul/23
Answered by witcher3 last updated on 24/Jul/23
![we applie S_n to this sum witch symetric Groupe of n element we not this elements σ cardS_n =n!;{1.....n}→^σ {1,....,n} S=Σ_(k_1 +...+k_n =m) (1/(2^k_1 (2^k_1 +2^k_2 )....(2^k_1 +2^k_2 +...+2^k_n ))) =Σ_(k_1 +...+k_n =m) (1/(2^k_(σ(1)) (2^k_(σ(1)) +2^k_(σ(2)) )....(2^k_1 +2^k_2 +...+2^k_n ))) S=(1/(n!))Σ_(σ∈S_n ) Σ_(k_1 +...+k_n =m) (1/(2^k_(σ(1)) (2^(σ(k_1 )) +2^(σ(k_2 )) )....(2^k_1 +2^k_2 +...+2^k_n ))) Σ_(σ∈S_n ) (1/(2^(σ(k_1 )) (2^(σ(k_1 )) +2^(σ(k_2 )) ).....(2^k_1 +...+2^k_n )))=(1/2^(k_1 +k_2 +..+k_n ) ) proof tack τ(1,2) transposition of 1 &2 2S_1 =Σ(1/(2^k_1 .....(2^k_1 +..2^k_n )))+(1/(2^k_2 (2^k_1 +2^k_2 )...(2^k_2 +2^k_1 ....+2^k_n ))) S_2 =2S_1 =(1/(2^(k_1 +k_2 ) (2^k_1 +2^k_2 +2^k_3 )(2^k_1 +...+2^k_n ))) S_2 τ(1,3)+S_2 τ(2,3)+S_2 =S_3 =3S_2 =(1/(2^(k_1 +k_2 +k_3 ) (2^k_1 +2^k_2 +2^k_3 +2^k_4 )...(2^k_1 +2^k_2 +..2^k_n ))) S^((t)) =Σ_(k=1) ^(t−1) S_(m−1) τ(1,t)+S_(m−1) =(1/(2^(k_1 +...+k_t ) .(2^k_1 +2^k_2 +..+2^k_(t+1) )..(2^k_1 +2^k_2 +..+2^k_n ))) S^n =nS_(n−1) =(1/2^(k_1 +...+k_n ) ) n!S=Σ_(k_1 +..+k_n =m) (1/2^(k_1 +...+k_n ) )=(1/2^m ) Σ_(k_1 +..+k_n =m) 1=(1/2^m ) (((m+n−1)),(( m)) ) S=( ((( m+n−1)),(( m)) )/(n!2^m )) “Σ_(σ∈S_n ) (1/(2^k_(σ(1)) (2^(kσ(1)) +2^(kσ(2)) )...(2^(kσ(1)) +2^(kσ(2)) +2^(kσ(n)) ))=(1/2^(k_1 +k_2 +..+k_n ) )” was the key σ[1..n]=[1...n]⇒2^(kσ(1)) +...+2^(kσ(n)) =2^k_1 +...+2^k_n σ is bijection](https://www.tinkutara.com/question/Q195109.png)
$$\mathrm{we}\:\mathrm{applie}\:\mathrm{S}_{\mathrm{n}} \:\mathrm{to}\:\mathrm{this}\:\mathrm{sum}\:\mathrm{witch}\:\mathrm{symetric}\:\mathrm{Groupe}\:\mathrm{of} \\ $$$$\mathrm{n}\:\mathrm{element}\:\mathrm{we}\:\mathrm{not}\:\mathrm{this}\:\mathrm{elements}\:\sigma \\ $$$$\mathrm{cardS}_{\mathrm{n}} =\mathrm{n}!;\left\{\mathrm{1}…..\mathrm{n}\right\}\overset{\sigma} {\rightarrow}\left\{\mathrm{1},….,\mathrm{n}\right\} \\ $$$$\mathrm{S}=\underset{\mathrm{k}_{\mathrm{1}} +…+\mathrm{k}_{\mathrm{n}} =\mathrm{m}} {\sum}\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } \left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } \right)….\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +…+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)} \\ $$$$=\underset{\mathrm{k}_{\mathrm{1}} +…+\mathrm{k}_{\mathrm{n}} =\mathrm{m}} {\sum}\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\sigma\left(\mathrm{1}\right)} } \left(\mathrm{2}^{\mathrm{k}_{\sigma\left(\mathrm{1}\right)} } +\mathrm{2}^{\mathrm{k}_{\sigma\left(\mathrm{2}\right)} } \right)….\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +…+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)} \\ $$$$\mathrm{S}=\frac{\mathrm{1}}{\mathrm{n}!}\underset{\sigma\in\mathrm{S}_{\mathrm{n}} } {\sum}\underset{\mathrm{k}_{\mathrm{1}} +…+\mathrm{k}_{\mathrm{n}} =\mathrm{m}} {\sum}\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\sigma\left(\mathrm{1}\right)} } \left(\mathrm{2}^{\sigma\left(\mathrm{k}_{\mathrm{1}} \right)} +\mathrm{2}^{\sigma\left(\mathrm{k}_{\mathrm{2}} \right)} \right)….\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +…+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)} \\ $$$$\underset{\sigma\in\mathrm{S}_{\mathrm{n}} } {\sum}\frac{\mathrm{1}}{\mathrm{2}^{\sigma\left(\mathrm{k}_{\mathrm{1}} \right)} \left(\mathrm{2}^{\sigma\left(\mathrm{k}_{\mathrm{1}} \right)} +\mathrm{2}^{\sigma\left(\mathrm{k}_{\mathrm{2}} \right)} \right)…..\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +…+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)}=\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} +\mathrm{k}_{\mathrm{2}} +..+\mathrm{k}_{\mathrm{n}} } } \\ $$$$\mathrm{proof}\: \\ $$$$\mathrm{tack}\:\tau\left(\mathrm{1},\mathrm{2}\right)\:\:\mathrm{transposition}\:\mathrm{of}\:\mathrm{1}\:\&\mathrm{2} \\ $$$$\mathrm{2S}_{\mathrm{1}} =\Sigma\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } …..\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +..\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)}+\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } \left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } \right)…\left(\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } ….+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)} \\ $$$$\mathrm{S}_{\mathrm{2}} =\mathrm{2S}_{\mathrm{1}} =\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} +\mathrm{k}_{\mathrm{2}} } \left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{3}} } \right)\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +…+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)} \\ $$$$\mathrm{S}_{\mathrm{2}} \tau\left(\mathrm{1},\mathrm{3}\right)+\mathrm{S}_{\mathrm{2}} \tau\left(\mathrm{2},\mathrm{3}\right)+\mathrm{S}_{\mathrm{2}} =\mathrm{S}_{\mathrm{3}} =\mathrm{3S}_{\mathrm{2}} =\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} +\mathrm{k}_{\mathrm{2}} +\mathrm{k}_{\mathrm{3}} } \left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{3}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{4}} } \right)…\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +..\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)} \\ $$$$\mathrm{S}^{\left(\mathrm{t}\right)} =\underset{\mathrm{k}=\mathrm{1}} {\overset{\mathrm{t}−\mathrm{1}} {\sum}}\mathrm{S}_{\mathrm{m}−\mathrm{1}} \tau\left(\mathrm{1},\mathrm{t}\right)+\mathrm{S}_{\mathrm{m}−\mathrm{1}} =\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} +…+\mathrm{k}_{\mathrm{t}} } .\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +..+\mathrm{2}^{\mathrm{k}_{\mathrm{t}+\mathrm{1}} } \right)..\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +..+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)} \\ $$$$\mathrm{S}^{\mathrm{n}} =\mathrm{nS}_{\mathrm{n}−\mathrm{1}} =\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} +…+\mathrm{k}_{\mathrm{n}} } } \\ $$$$\mathrm{n}!\mathrm{S}=\underset{\mathrm{k}_{\mathrm{1}} +..+\mathrm{k}_{\mathrm{n}} =\mathrm{m}} {\sum}\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} +…+\mathrm{k}_{\mathrm{n}} } }=\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{m}} }\:\:\underset{\mathrm{k}_{\mathrm{1}} +..+\mathrm{k}_{\mathrm{n}} =\mathrm{m}} {\sum}\mathrm{1}=\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{m}} }\begin{pmatrix}{\mathrm{m}+\mathrm{n}−\mathrm{1}}\\{\:\:\:\:\:\:\:\mathrm{m}}\end{pmatrix} \\ $$$$\mathrm{S}=\frac{\begin{pmatrix}{\:\:\:\mathrm{m}+\mathrm{n}−\mathrm{1}}\\{\:\:\:\:\:\:\:\:\:\:\mathrm{m}}\end{pmatrix}}{\mathrm{n}!\mathrm{2}^{\mathrm{m}} } \\ $$$$“\underset{\sigma\in\mathrm{S}_{\mathrm{n}} } {\sum}\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\sigma\left(\mathrm{1}\right)} } \left(\mathrm{2}^{\mathrm{k}\sigma\left(\mathrm{1}\right)} +\mathrm{2}^{\mathrm{k}\sigma\left(\mathrm{2}\right)} \right)…\left(\mathrm{2}^{\mathrm{k}\sigma\left(\mathrm{1}\right)} +\mathrm{2}^{\mathrm{k}\sigma\left(\mathrm{2}\right)} +\mathrm{2}^{\mathrm{k}\sigma\left(\mathrm{n}\right)} \right.}=\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} +\mathrm{k}_{\mathrm{2}} +..+\mathrm{k}_{\mathrm{n}} } }'' \\ $$$$\mathrm{was}\:\mathrm{the}\:\mathrm{key} \\ $$$$\sigma\left[\mathrm{1}..\mathrm{n}\right]=\left[\mathrm{1}…\mathrm{n}\right]\Rightarrow\mathrm{2}^{\mathrm{k}\sigma\left(\mathrm{1}\right)} +…+\mathrm{2}^{\mathrm{k}\sigma\left(\mathrm{n}\right)} =\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +…+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \:\sigma\:\mathrm{is}\:\mathrm{bijection} \\ $$$$ \\ $$$$ \\ $$$$ \\ $$$$ \\ $$$$ \\ $$
Commented by witcher3 last updated on 24/Jul/23
$$\mathrm{car}\:\left(\mathrm{k}_{\mathrm{1}} ,\mathrm{k}_{\mathrm{2}} …\mathrm{k}_{\mathrm{n}} \right)\mid\left(\mathrm{k}_{\mathrm{1}} +…+\mathrm{k}_{\mathrm{n}} =\mathrm{m}\right)=\begin{pmatrix}{\mathrm{m}+\mathrm{n}−\mathrm{1}}\\{\:\:\:\:\:\:\:\mathrm{m}}\end{pmatrix} \\ $$