For the Collatz function $$T(n)=\frac {3n+1}{2} \text {if} \ n \ \text{is odd}$$ and $$T(n)=\frac {n}{2} \text {if} \ n \ \text{is even }$$ I have found that $$ \sum _{k=1}^{2n} T(k) = \sum _{k=1}^{2n} k$$

Proof:$$ \sum _{k=1}^{2n} T(k) = \{T(1)+T(3)+T(5)+...+T(2n-1)\} + \{T(2) +T(4) +...+T(2n)\} $$

$$= \frac {3(1)+1}{2} +\frac {3(3)+1}{2}+...+\frac {3(2n-1)+1}{2} +1+2+3+...+n $$

$$= \frac {3n^2 +n}{2} + \frac {n(n+1)}{2} = n(2n+1)=\sum _{k=1}^{2n} k.$$

Question: Are there other non-trivial sets $S$ which satisfy $$ \sum _{k\in S}T(k) = \sum _{k\in S} k$$

  • 2
    $\begingroup$ This is a simple extension of your proof, but by linearity of sums since you have shown that $T(k)-k$ sums to zero on $S=[1,...,2n]$ for all $n$, we can take differences (or just calculate easily) to see that the same is true for $\{2n-1,2n\}$ and sum up to see that whenever $S$ is a finite set of adjacent odd-even pairs like $\{1,2,5,6,17,18\}$ then this property holds. So maybe a better question is whether there are any sets $S$ which are not of this form. $\endgroup$ – Mario Carneiro Jul 11 '18 at 0:56
  • $\begingroup$ This $n-(-1)^n$ maybe? $\endgroup$ – Natural Number Guy Jul 11 '18 at 1:44

There are many such sets.

For $S\subseteq\mathbb N$, let the even-odd decomposition of $S$ be the unique sets $A,B$ such that $S=\{2n-1\mid n\in A\}\cup \{2n\mid n\in B\}$.

Theorem: A set $S$ satisfies $\sum_{n\in S}T(n)=\sum_{n\in S}n$ if and only the sets $A,B$ in the even odd decomposition of $S$ have equal sum.

This immediately produces many examples, just by picking sets with the same sum like $A=\{1,2,6\}$ and $B=\{2,3,4\}$ and combining them into $S=\{1,3,4,6,8,11\}$.

Proof: \begin{align} \sum_{n\in S}(T(n)-n)&=\sum_{n\in A}(T(2n-1)-(2n-1))+\sum_{n\in B}(T(2n)-2n)\\ &=\sum_{n\in A}\left[\frac{3(2n-1)+1}{2}-(2n-1)\right]+\sum_{n\in B}(n-2n)\\ &=\sum_{n\in A}n-\sum_{n\in B}n \end{align} Therefore $\sum_{n\in S}(T(n)-n)=0$ if and only if $\sum_{n\in A}n=\sum_{n\in B}n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.