|
original poster
abababa
posted 2022-6-9 20:07
是的,我证出来了。就是有那个递推,然后用数学归纳法就能证明了。不过用递推不好想,看了2楼的提示才想到用递推的。
以下总设$i_1\ge i_2\ge\cdots$。设$n$的表示方法数为$f(n)$。
设$2n+1=2^{i_1}+2^{i_2}+\cdots+2^{i_r}+1$,这个表示方式对应了$2n$的一种表示方式$2n=2^{i_1}+2^{i_2}+\cdots+2^{i_r}$,它是双射,所以$f(2n+1)=f(2n)$。
再将$2n$的表示法分为两类,一类含有$1$而另一类不含$1$,令两类表示法分别组成集合$A,B$,显然$A\cap B=\varnothing$。对$A$中的元素$2n=2^{i_1}+2^{i_2}+\cdots+2^{i_r}+1$,此元素对应$2n-1$的一种表示$2n-1=2^{i_1}+2^{i_2}+\cdots+2^{i_r}$。对$B$中的元素$2n=2^{i_1}+2^{i_2}+\cdots+2^{i_r}$,此元素对应$n$的一种表示$n=2^{i_1-1}+2^{i_2-1}+\cdots+2^{i_r-1}$。这两组对应都是双射,于是还有$f(2n)=f(2n-1)+f(n)$。
当$n=2$时显然$f(n)=2$,是偶数,假设当$n=2,3,\cdots,k$时$f(n)$都是偶数,则当$n=k+1$时:若$k=2m$,则$f(k+1)=f(2m+1)=f(2m)=f(2m-1)+f(m)$,由于$2\le2m-1, m\le k$,由归纳假设知$f(2m-1),f(m)$都是偶数,于是$f(n)$为偶数。若$k=2m+1$,则$f(k+1)=f(2m+2)=f(2(m+1))=f(2m+1)+f(m+1)$,由于$2\le2m+1, m+1\le k$,由归纳假设知$f(2m+1),f(m+1)$都是偶数,于是$f(n)$也为偶数。 |
|