Question

Golomb’s self-generating sequence is the unique non-decreasing sequence of positive integers ${\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{,}{\mathit{a}}_{\mathbf{3}}$that has the property that it contains exactly ${\mathit{a}}_{\mathbf{k}}$occurrence k of for each positive integer k .

Show that if f (n) is the largest integer m such that${\mathit{a}}_{\mathbf{m}}\mathbf{=}\mathit{n}$ , where is the term of Golomb’s self-generating sequence, then$\mathit{f}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{=}\mathbf{\sum }_{\mathbf{k}\mathbf{=}\mathbf{1}}^{\mathbf{n}}\mathbf{ }{\mathit{a}}_{\mathbf{k}}$ and$\mathit{f}\mathbf{\left(}\mathit{f}\mathbf{\right(}\mathit{n}\mathbf{\left)}\mathbf{\right)}\mathbf{=}\mathbf{\sum }_{\mathbf{k}\mathbf{=}\mathbf{1}}^{\mathbf{n}}\mathbf{ }{\mathit{a}}_{\mathbf{k}}$

Short answer

It is proved that$f\left(n\right)=\sum _{k=1}^n a_k\text{and}f\left(f\right(n\left)\right)=\sum _{k=1}^n k\cdot a_k$

Step-by-step solution

Golomb’s self-generating sequence

Non-decreasing Golomb’s self-generating sequence is given by

${\mathit{a}}_{\mathbf{k}}\mathbf{\le }{\mathit{a}}_{\mathbf{k}\mathbf{+}\mathbf{1}}$

Exactly occurrences of means that if ${\mathit{a}}_{\mathbf{k}}\mathbf{=}\mathit{n}$then k must appear exactly times in a sequence.

Proving that f(n)=∑k=1n ak and f(f(n))=∑k=1n ak 

Let be a positive integer.

The largest integer m such that$a_m=n$is the sum of the counts of 1 to n .

So,

$\begin{array}{r}f\left(n\right)=m=1+2+3+\dots +n\\ =a_1+a_2+\dots +a_n\\ =\sum _{k=1}^n a_k\end{array}$

However, this implies that f (f(n)) is the sum of the first f (n) terms of the sequence.

Solve further as:

$\begin{array}{r}f\left(f\right(n\left)\right)=\sum _{k=1}^n f\left(a_k\right)\\ =\sum _{k=1}^n \sum _{l=1}^k a_l\\ =\sum _{k=1}^n k\cdot a_k\end{array}$

Hence proved.