每日一题[887]发现递推关系

定义$g(n)$为自然数$n$中所有因数中的最大奇数，求

$$M(n)=g(1)+g(2)+\cdots+g\left(2^n-1\right)$$ 的值．

---

分析与解　注意到$g(2n)=g(n)$，记

$$S_n=g(1)+g(2)+\cdots+g\left(2^n-1\right)+g\left(2^n\right),$$ 则当$n\geqslant 2$时，有 $$\begin{split} S_n&=g(1)+g(3)+\cdots+g\left(2^n-1\right)+\left[g(2)+g(4)+\cdots+g\left(2^n\right)\right]\\&=1+3+\cdots+\left(2^n-1\right)+\left[g(1)+g(2)+\cdots+g\left(2^{n-1}\right)\right]\\&=2^{2n-2}+S_{n-1}, \end{split}$$ 而$S_1=2$，由累加法得到 $$S_n=2+2^2+2^4+2^6+\cdots+2^{2n-2}=2+\dfrac 43\left(4^{n-1}-1\right),$$ 进而可得 $$M(n)=S_n-1=\dfrac 13\cdot 4^n-\dfrac 13.$$