じゃんけんの期待回数について

$n>1$のとき、マルコフ性より、
$$\begin{array}{rl}& E(n)=\sum _{i=1}^{n}p(n,i)(E(i)+1)\\ & ⟺(1-p(n,n))E(n)=1+\sum _{i=1}^{n-1}p(n,i)E(i)(\because \sum _{i=1}^{n}p(n,i)=1)\end{array}$$
$p(n,n)\ne$$1$　として
$$\begin{array}{r}E(n)=\frac{1}{1-p(n,n)}(1+\sum _{i=1}^{n-1}p(n,i)E(i))\end{array}$$を得る。

$a$$>$$b$のときは略
$a=b$のとき、$p(a,b)$はつまりあいこになる確率。
$$\begin{array}{rl}p(a,a)& =1-\sum _{i=1}^{a-1}p(a,i)\\ & =1-\sum _{i=0}^a\frac{1}{3^{a-1}}(\genfrac{}{}{0ex}{}{a}{i})+\frac{2}{3^{a-1}}\\ & =1-\frac{2^a-2}{3^{a-1}}\end{array}$$
よって、補題１より、$E(n)$の漸化式を得る。

https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1205-9.pdf
をご参照ください。
補題２で得られた漸化式を用いて帰納的に証明できます。
具体的な形は
${\displaystyle \frac{1}{3}}({\displaystyle \frac{3}{2}}{)}^n\le E(n)$$\le$ $({\displaystyle \frac{3}{2}}{)}^n$
です。

$a>b$のとき　略
$a=b$のとき、つまりあいこになる確率は、参加者が全員王様に勝利するか、全員あいこor負けとなる確率なので、
$p(a,a)=({\displaystyle \frac{2}{3}}{)}^a+({\displaystyle \frac{1}{3}}{)}^a$
よって、補題１より$K(n)$の漸化式を得る。

①$K(n)=O({\log }_{3}n)$ の証明

$\mathrm{\forall }n$$\in$$\mathbb{N}$について$K(n)\le an+b$ と仮定する。($a,b=const.$)
このとき補題４より、1より大きい自然数$n$に対し
$$\begin{array}{rl}K(n)& ={\displaystyle \frac{1}{3^n-2^n-1}}(3^n+\sum _{i=1}^{n-1}{2}^{n-i}{\displaystyle (\genfrac{}{}{0ex}{}{n}{i})}K(i))\\ & \le {\displaystyle \frac{1}{3^n-2^n-1}}(3^n+\sum _{i=2}^{n-1}{2}^{n-i}{\displaystyle (\genfrac{}{}{0ex}{}{n}{i})}(ai+b))\\ & ={\displaystyle \frac{1}{3^n-2^n-1}}(3^n+\sum _{i=0}^n{2}^{n-i}{\displaystyle (\genfrac{}{}{0ex}{}{n}{i})}(ai+b)-(an+b)-2^{n-1}(a+b)n-2^{n}b)\\ & ={\displaystyle \frac{1}{3^n-2^n-1}}(3^n+3^{n-1}an+3^{n}b-(an+b)-2^{n-1}(a+b)n-2^{n}b)\\ & ={\displaystyle \frac{1}{3^n-2^n-1}}(3^n+an(3^{n-1}-2^{n-1}-1)+b(3^n-2^n-1)-2^{n-1}bn)\\ & ={\displaystyle \frac{1}{3^n-2^n-1}}(3^n+{\displaystyle \frac{an}{3}}(3^n-2^n-1)+b(3^n-2^n-1)-{\displaystyle \frac{2^n}{6}}an-{\displaystyle \frac{2}{3}}an-2^{n-1}b)\\ & \le \frac{1}{3}an+b+1\end{array}$$
これを繰り返すことで、$\mathrm{\forall }t\in \mathbb{N}$ に対し
$K(n)\le ({\displaystyle \frac{1}{3}}{)}^{t}an+t+b$が成り立つ。
よって　$t=\lceil {\log }_{3}n\rceil$　とおくと、
$$\begin{array}{rlr}K(n)& \le ({\displaystyle \frac{1}{3}}{)}^{\lceil {\log }_{3}n\rceil }an+\lceil {\log }_{3}n\rceil +b& \le ({\displaystyle \frac{1}{3}}{)}^{{\log }_{3}n}an+{\log }_{3}n+1+b\\ & ={\log }_{3}n+a+b+1\end{array}$$
$K(n)\le 2n$であることは帰納法で簡単に示せるので、
$K(n)\le {\log }_{3}n+3$
したがって　$K(n)=O({\log }_{3}n)$を得る。

②$K(n)=\mathrm{\Omega }({\log }_{3}n)$の証明
本筋は①と同じです。
$\mathrm{\forall }n\in \mathbb{N}$に対して、
$K(n)\ge {\displaystyle \frac{a}{n+1}}+b$が成り立つと仮定する。このとき、1より大きい$n$について
$$\begin{array}{rl}K(n)& ={\displaystyle \frac{1}{3^n-2^n-1}}(3^n+\sum _{i=1}^{n-1}{2}^{n-i}{\displaystyle (\genfrac{}{}{0ex}{}{n}{i})}K(i))\\ & \ge {\displaystyle \frac{1}{3^n-2^n-1}}(3^n+\sum _{i=0}^n{2}^{n-i}{\displaystyle (\genfrac{}{}{0ex}{}{n}{i})}(\frac{a}{n+1}+b)-2^n(a+b)-(\frac{a}{n+1}+b))\\ & \ge {\displaystyle \frac{1}{3^n-2^n-1}}(3^n+\frac{3^{n+1}a}{n+1}+3^{n}b-2^n(a+b)-(\frac{a}{n+1}+b))\\ & =\frac{1}{3^n-2^n-1}(3^n+\frac{3a}{n+1}(3^n-2^n-1)+b(3^n-2^n-1)+\frac{3a\times 2^n}{n+1}+\frac{3a}{n+1})\\ & =\frac{3a}{n+1}+b+\frac{(n+1)3^n+3a\times 2^n+3a}{(n+1)(3^n-2^n-1)}\\ & \ge \frac{3a}{n+1}+b+1\end{array}$$
よって帰納的に$\mathrm{\forall }t\in \mathbb{N}$に対して
$K(n)\ge {\displaystyle \frac{a{3}^t}{n+1}}+t+b$ を得る。
$t=\lceil {\log }_{3}n\rceil$とおくと、]
$K(n)\ge {\log }_3(n+1)+a+b$
$\mathrm{\forall }n\in \mathbb{N}$ について
$K(n)\ge {\displaystyle \frac{1}{n+1}}-1$が成り立つことは簡単に示せるので、$a=1, b=-1$　として
$K(n)\ge {\log }_3(n+1)\ge {\log }_{3}n$
したがって、　$K(n)=\mathrm{\Omega }({\log }_{3}n)$ を得る。
①、②より、
${\log }_3(n+1)\le K(n)\le {\log }_{3}n+3$ $(n\ge 2)$
すなわち$K(n)=\mathrm{\Theta }({\log }_{3}n)$　　　　　　（証明終）

$n$は１より大きい自然数とする。
$$\begin{array}{rl}& {\log }_3(n+1)\le K(n)\le {\log }_{3}n+3\\ & ⟺\frac{{\log }_3(n+1)}{{\log }_{3}n}\le \frac{K(n)}{{\log }_{3}n}\le 1+\frac{3}{{\log }_{3}n}\end{array}$$
$n\to \infty$で右辺と左辺は共に１に収束する。
よってハサミウチの原理より
$$\begin{array}{r}\underset{n\to \mathrm{\infty }}{lim}{\displaystyle \frac{K(n)}{{\log }_{3}n}}=1\end{array}$$

$n\ge 7$のとき
$K(n)<{\log }_{3}n+3<{\displaystyle \frac{1}{3}}({\displaystyle \frac{3}{2}}{)}^n<E(n)$
なので、あとは$6$以下の$n$について調べることで系２を得る。