中山大学 2023年强基第1题
📝 题目
已知 $n \in \mathbb{N}^{*}$ ，求 $\displaystyle \sum_{k=0}^{n}\left[\frac{n+2^{k}}{2^{k+1}}\right]$ 。
💡 答案解析
【解析】考虑一个细节，记 $n=\sum_{i=0}^{m} a_{i} \cdot 2^{i}$ ，其中 $a_{i} \in\{0,1\}$ ，则 $\displaystyle \frac{n+2^{k}}{2^{k+1}}=\sum_{i=k+1}^{m} a_{i} 2^{i-k-1}+\frac{1+a_{k}}{2} +\frac{\sum_{i=0}^{k-1} a_{i} 2^{i}}{2^{k+1}}$ 。而对于后面的部分是严格小于 $\displaystyle \frac{1}{2}$ ，因此若重新记 $n=2^{k_{1}}+2^{k_{2}}+\cdots+2^{k_{m}}$ ，其中 $k_{1}\lt k_{2}\lt \cdots\lt k_{m}$ ，则 $\displaystyle \sum_{k=0}^{n}\left[\frac{n+2^{k}}{2^{k+1}}\right]=\left(2^{k_{1}-1}+2^{k_{1}-2}+\cdots 2^{0}+1\right)+\left(2^{k_{2}-1}+2^{k_{2}-2}+\cdots 2^{0}+1\right)+ \cdots+\left(2^{k_{m}-1}+2^{k_{m}-2}+\cdots 2^{0}+1\right)=2^{k_{1}}+2^{k_{2}}+\cdots+2^{k_{m}}=n$ 。
📋 详细解题步骤
步骤 1/5
目标：将n表示为二进制形式
设n的二进制表示为n=∑_{i=0}^m a_i·2^i，其中a_i∈{0,1}。
公式：n=∑_{i=0}^m a_i·2^i
提示：二进制表示是处理与2的幂相关问题的常用技巧。
步骤 2/5
目标：将求和项中的分数拆解
将(n+2^k)/2^{k+1}拆分为三部分：∑_{i=k+1}^m a_i·2^{i-k-1} + (1+a_k)/2 + (∑_{i=0}^{k-1} a_i·2^i)/2^{k+1}。
公式：(n+2^k)/2^{k+1} = ∑_{i=k+1}^m a_i·2^{i-k-1} + (1+a_k)/2 + (∑_{i=0}^{k-1} a_i·2^i)/2^{k+1}
提示：注意第三部分严格小于1/2。
步骤 3/5
目标：确定取整后的值
由于第三部分小于1/2，取整后为∑_{i=k+1}^m a_i·2^{i-k-1} + [(1+a_k)/2]。而[(1+a_k)/2]等于1当a_k=1，等于0当a_k=0。
公式：[ (n+2^k)/2^{k+1} ] = ∑_{i=k+1}^m a_i·2^{i-k-1} + a_k
提示：注意a_k为0或1，因此(1+a_k)/2的整数部分就是a_k。
步骤 4/5
目标：将n表示为2的幂之和
设n=2^{k_1}+2^{k_2}+...+2^{k_m}，其中k_1
公式：n=2^{k_1}+2^{k_2}+...+2^{k_m}
提示：这是二进制表示的另一种写法。
步骤 5/5
目标：计算求和结果
对于每个k_j，当k从0到k_j-1时，a_k=0，但注意当k=k_j时，a_k=1，且∑_{i=k+1}^m a_i·2^{i-k-1}在k
公式：∑_{k=0}^n [ (n+2^k)/2^{k+1} ] = n
提示：可以验证：当n=0时，和为0；当n=1时，和为1。
📷 拍照上传批改
拍照上传批改功能已预留入口，后续接入图片上传、OCR识别与AI批改。