Forgot password
 Register account
View 238|Reply 2

[数论] 将n表示为2的非负整数幂之和,表示方法为f(n),求证2|f(n)

[Copy link]

414

Threads

1641

Posts

15

Reputation

Show all posts

abababa posted 2022-6-9 15:12 |Read mode
Last edited by abababa 2022-6-9 20:10将$n\ge2$表示为$2$的非负整数次幂之和,仅求和次序不同时,视为同一种表示,表示方法的总数记为$f(n)$。求证$2\mid f(n)$。

3200

Threads

7827

Posts

52

Reputation

Show all posts

hbghlyj posted 2022-6-9 18:47
oeis.org/A018819
從下面的遞推式可以得到1樓的$a_n(n⩾2)$為偶數 $$a_n = \cases{a_{2m}&if $n=2m+1$\\a_{2m-1} + a_m&if $n=2m$}$$
a(2m+1) = a(2m), a(2m) = a(2m-1) + a(m).
Proof: If n is odd there is a part of size 1; removing it gives a partition of n - 1. If n is even either there is a part of size 1, whose removal gives a partition of n - 1, or else all parts have even sizes and dividing each part by 2 gives a partition of n/2.
$n$ 表為 2 的幂之和。如果 $n$ 是奇數,則有一項是 1 ,刪除它會得到一個 $n - 1$ 的表示。如果 $n$ 是偶數,或者有一項是 1 ,刪除它得到一個 $n - 1$ 的表示;或者所有的項都是偶數,並且將每項除以 2 得到一個 $n/2$ 的表示。


另一個有趣的遞推式
a(n) = 1 if n = 0, Sum(j = 0..[n/2], a(j)) if n > 0. - David W. Wilson, Aug 16 2007
$$a_n = \left\{ \begin{array} { l l } { 1 } & { \text { if } n = 0 } \\ { \sum _ { j = 0 } ^ {\lfloor n / 2\rfloor } a_j } & { \text { if } n > 0 } \end{array} \right.$$ 如何證明呢

414

Threads

1641

Posts

15

Reputation

Show all posts

original poster abababa posted 2022-6-9 20:07
hbghlyj 发表于 2022-6-9 18:47
本帖最后由 hbghlyj 于 2022-6-9 12:12 编辑 http://oeis.org/A018819
從下面的遞推式可以得到1樓的$a_n(n ...
是的,我证出来了。就是有那个递推,然后用数学归纳法就能证明了。不过用递推不好想,看了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)$也为偶数。

Quick Reply

Advanced Mode
B Color Image Link Quote Code Smilies
You have to log in before you can reply Login | Register account

$\LaTeX$ formula tutorial

Mobile version

2025-7-15 14:47 GMT+8

Powered by Discuz!

Processed in 0.012856 seconds, 23 queries