재귀적 규칙

다음과 같은 수열을 생각해보자.

$0\ 1\ 0\ 2\ 0\ 1\ 0\ 3\ 0\ 1\ 0\ 2\cdot\cdot\cdot$

$0$이 아닌 항들을 모아보면

$1\ 2\ 1\ 3\ 1\ 2$

위의 수열 $+1$이다.

또 여기서 $1$이 아닌 항들을 모아보면

$2\ 3\ 2$

다시 위의 수열 $+1$이다.

이 포스팅의 제목이 재귀적 규칙인 이유이다.

 

위 수열을 정의해보자.

수열 $\left\{k_{i\ n}\right\}$를 다음과 같이 정의한다.

$1$이 아닌 자연수 $m$과 임의의 자연수 $\lambda$에 대해

$k_{1}=1,\ 2,\ 3,\ 4\cdot\cdot\cdot$

$k_{i}=m^{\lambda(i-1)}k_{1}$

$\left\{p_{i}\right\}$는 

$p_{i}=\log_{m}\frac{k_{i}}{k_{1}}=\lambda(i-1)$

$\left\{a_{i\ n}\right\}$는

$a_{i\ n}=p_{i}+\max(q)\ (m^{q}|k_{1\ n})$

으로 정의된다.

 

이제 이 정의된 수열이 어떤 특성을 가지는지 알아보자.

$a_{i}=a_{j}+\lambda(i-j)$

 

<증명>

$a_{i\ n}=p_{i}+\max(q)\ (2^{q}|k_{1\ n})$

$a_{j\ n}=p_{j}+\max(q)\ (2^{q}|k_{1\ n})$

$a_{i\ n}-a_{j\ n}=p_{i}-p_{j}=\lambda(i-1)-\lambda(j-1)=\lambda(i-j)$

$\lambda=1$ 일때 다음과 같은 정리를 얻는다.

 

<정리>

임의의 자연수 $\alpha,\ \beta,\ m(\neq 1),\ k$에 대하여

$a_{\alpha\ k}-a_{\beta\ k}=\lambda(\alpha-\beta)$

이다.

 

이렇게 수열을 만들고 나니 뭔가 계산해보고 싶어졌다.

어떤 자연수 $N$이 주어질 때 $1$부터 $N$까지 $a_{1}$의 합은 얼마일까?

우선 계산 아이디어를 설명하겠다.

예)$m=2,\ N=24$

$0\ 1\ 0\ 2\ 0\ 1\ 0\ 3\ 0\ 1\ 0\ 2\ 0\ 1\ 0\ 4\ 0\ 1\ 0\ 2\ 0\ 1\ 0\ 3$

$m$개씩 묶는다.

$(0\ 1)\ (0\ 2)\ (0\ 1)\ (0\ 3)\ (0\ 1)\ (0\ 2)\ (0\ 1)\ (0\ 4)\ (0\ 1)\ (0\ 2)\ (0\ 1)\ (0\ 3)$

$\lfloor\frac{N}{m}\rfloor$개의 $0$이 있다.

$1\ 2\ 1\ 3\ 1\ 2\ 1\ 4\ 1\ 2\ 1\ 3$

$m$개씩 묶는다.

$(1\ 2)\ (1\ 3)\ (1\ 2)\ (1\ 4)\ (1\ 2)\ (1\ 3)$

여기서 우리는 보조 정리를 사용할 것이다.

 

<보조 정리>

$\lfloor\frac{\lfloor\frac{N}{m}\rfloor}{m}\rfloor=\lfloor\frac{N}{m^{2}}\rfloor$

 

보조 정리에 의해 $1$은 $\lfloor\frac{N}{m^{2}}\rfloor$개 있다.

$2\ 3\ 2\ 4\ 2\ 3$

$m$개씩 묶는다.

$(2\ 3)\ (2\ 4)\ (2\ 3)$

$\lfloor\frac{N}{m^{3}}\rfloor$개의 $2$가 있다.

반면 묶이지 않은 $2$는 $\lfloor\frac{N}{m^{2}}\rfloor-m\lfloor\frac{N}{m^{3}}\rfloor$개 있다.

$(3\ 4)\ 3$

$\lfloor\frac{N}{m^{4}}\rfloor$개의 $3$이 있다.

반면 묶이지 않은 $3$은 $\lfloor\frac{N}{m^{3}}\rfloor-m\lfloor\frac{N}{m^{4}}\rfloor$개 있다.

$4$

묶지 못한다.

묶이지 않은 $4$는 $\lfloor\frac{N}{m^{4}}\rfloor-m\lfloor\frac{N}{m^{5}}\rfloor$개 있다.

 

<일반화>

우리가 구하고자 하는 답이 $s$라면

$s=\lfloor\frac{N}{m}\rfloor(m-1)\times 0+(N-m\lfloor\frac{N}{m}\rfloor)\times 0+\lfloor\frac{N}{m^{2}}\rfloor(m-1)\times 1+(\lfloor\frac{N}{m}\rfloor-m\lfloor\frac{N}{m^{2}}\rfloor)\times 1+\cdot\cdot\cdot$

여기서 잠시 의문이 들것이다.

'왜 $m-1$을 곱한것인가?'

$m=3$인 수열을 생각해보자

$0\ 0\ 1\ 0\ 0\ 1\ 0\ 0\ 3\ 0\ 0\ 1\cdot\cdot\cdot$

$3$개씩 묶게 되면 $0$은 $2$개씩 생긴다. 

$m$개씩 묶는다면 $0$은 $m-1$개씩 생긴다.

 

이제 식을 간결하게 만들어보자.

 식을 좀 더 수정하면

식이 정말 깔끔해졌다는 사실을 알 수 있다.

합의 기호의 윗부분이 비어있는데 합의 기호 내부의 항이 $0$이 되면 중단하면 되기 때문이다.

또, $1$부터 $N$까지의 $a_{1}$의 합은 $N!=m^{s}k,\ (m,k)=1$ 일 때의 $s$값이라고도 생각해볼 수 있다.

 

지금까지 우리가 합에 대해서 계산해봤는데 이제 곱에 대해서도 생각해볼 수 있지 않을까?

이는 추후 연구 예정에 있다.