오일러 변환

1. 개요

오일러 변환은 수열에 이항 변환을 적용하여 정의되며, 교대급수의 수렴을 가속화하는 데 사용된다. 이항 변환은 수열 {an}을 다른 수열 {sn}으로 변환하는 것으로, 수열의 전방 차분과 관련이 있다. 오일러 변환은 일반화될 수 있으며, 교대급수, 초 기하 급수, 연분수 등 다양한 수학적 개념과 연관되어 있다. 또한, 이항 컨볼루션, 생성 함수, 적분 표현 등과도 관계를 맺는다.

2. 정의

오일러 변환은 수열에 이항 변환을 적용하여 정의된다.

:$E\_a\; =\; \backslash sum\_\{k=0\}^\backslash infty\; \backslash frac\{\backslash Delta^k\; a\_0\}\{2^\{k+1\}\}$

(하위 섹션 "오일러 변환"에서 이항 변환을 적용한 결과를 상세히 설명하고 있으므로, 여기서는 정의만 간략하게 언급한다.)

2.1. 이항 변환

수열 \{{a_n}\}의 이항 변환 T는 다음과 같이 정의되는 수열 \{{s_n}\}이다.

:$s\_n\; =\; \backslash sum\_\{k=0\}^n\; (-1)^k\; \{n\backslash choose\; k\}\; a\_k.$

이는 형식적으로 다음과 같이 쓸 수 있다.

:$s\_n\; =\; (Ta)\_n\; =\; \backslash sum\_\{k=0\}^n\; T\_\{nk\}\; a\_k$

여기서 T는 행렬 요소 T_nk를 갖는 무한 차원 연산자이다. 이 변환은 대합이므로,

:$TT\; =\; 1$

또는 지수 표기법으로 나타내면,

:$\backslash sum\_\{k=0\}^\backslash infty\; T\_\{nk\}T\_\{km\}\; =\; \backslash delta\_\{nm\}$

과 같다. 여기서 $\backslash delta\_\{nm\}$은 크로네커 델타이다. 원래의 수열은 다음과 같이 다시 얻을 수 있다.

:$a\_n=\backslash sum\_\{k=0\}^n\; (-1)^k\; \{n\backslash choose\; k\}\; s\_k.$

수열의 이항 변환은 그 수열의 n번째 전방 차분이며, 홀수 차분에는 음수 부호가 붙는다. 즉, 다음과 같다.

:$\backslash begin\{align\}$
s_0 &= a_0 \\
s_1 &= - (\Delta a)_0 = -a_1+a_0 \\
s_2 &= (\Delta^2 a)_0 = -(-a_2+a_1)+(-a_1+a_0) = a_2-2a_1+a_0 \\
&\;\; \vdots \\
s_n &= (-1)^n (\Delta^n a)_0
\end{align}

여기서 Δ는 전방 차분 연산자이다.

일부 저자는 이항 변환을 다음과 같이 정의하여 자기 반전되지 않도록 한다.

:$t\_n\; =\; \backslash sum\_\{k=0\}^n\; (-1)^\{n-k\}\; \{n\backslash choose\; k\}\; a\_k$

그 역은 다음과 같다.

:$a\_n=\backslash sum\_\{k=0\}^n\; \{n\backslash choose\; k\}\; t\_k.$

이 경우 전자의 변환을 역 이항 변환이라고 하고, 후자를 단순히 이항 변환이라고 한다. 이는 정수열 온라인 백과사전 등에서 표준적으로 사용된다.

2.2. 오일러 변환

수열 $\backslash \{a\_n\backslash \}$에 이항 변환 $\backslash Delta^n$을 적용하여 오일러 변환을 정의하면 다음과 같다.

:$E\_a\; =\; \backslash sum\_\{k=0\}^\backslash infty\; \backslash frac\{\backslash Delta^k\; a\_0\}\{2^\{k+1\}\}$

만약 급수 $\backslash sum\_\{k=0\}^\backslash infty\; (-1)^k\; a\_k$ 가 수렴하면, 오일러 변환 $E\_a$ 도 역시 수렴하고, $\backslash sum\_\{k=0\}^\backslash infty\; (-1)^k\; a\_k\; =\; E\_a$ 가 성립한다. 즉, 교대급수 판정법에 의해 $\backslash \{a\_n\backslash \}$ 이 0으로 수렴하는 감소수열이기만 하면 오일러 변환은 수렴하고, 위 정리를 이용할 수 있다.

예를 들어, 교대급수 $\backslash sum\_\{k=0\}^\backslash infty\; (-1)^k\; \backslash frac\{1\}\{1+k\}$ 의 값을 오일러 변환을 이용해 구할 수 있다. 수열 $a\_n\; =\; \backslash frac\{1\}\{1+n\}$ 에 이항 변환을 적용하면 다음과 같다.

:$\backslash Delta^0\; a\_0\; =\; 1$
:$\backslash Delta^1\; a\_0\; =\; 1\; -\; \backslash frac\{1\}\{2\}\; =\; \backslash frac\{1\}\{2\}$
:$\backslash Delta^2\; a\_0\; =\; 1\; -\; \backslash frac\{2\}\{2\}\; +\; \backslash frac\{1\}\{3\}\; =\; \backslash frac\{1\}\{3\}$
:$\backslash Delta^3\; a\_0\; =\; 1\; -\; \backslash frac\{3\}\{2\}\; +\; \backslash frac\{3\}\{3\}\; -\; \backslash frac\{1\}\{4\}\; =\; \backslash frac\{1\}\{4\}$
...
:$\backslash Delta^n\; a\_0\; =\; \backslash frac\{1\}\{n+1\}$

따라서, $\backslash \{a\_n\backslash \}$ 의 오일러 변환은

:$E\_a\; =\; \backslash sum\_\{k=0\}^\backslash infty\; \backslash frac\{\backslash Delta^k\; a\_0\}\{2^\{k+1\}\}\; =\; \backslash sum\_\{k=0\}^\backslash infty\; \backslash frac\{1\}\{(k+1)2^\{k+1\}\}$

이 되고, 이 값은 $\backslash log\; 2$ 가 된다.

수열의 생성함수 간의 관계는 때때로 오일러 변환이라고 불리며, 교대 급수의 수렴을 가속화하는 데 사용된다. 다음 등식이 성립한다.

:$\backslash sum\_\{n=0\}^\backslash infty\; (-1)^n\; a\_n\; =\; \backslash sum\_\{n=0\}^\backslash infty\; (-1)^n\; \backslash frac\{(\backslash Delta^n\; a)\_0\}\{2^\{n+1\}\}$

이는 위 공식의 마지막 부분에 x = 1/2를 대입하여 얻어진다. 우변의 항들은 일반적으로 훨씬 더 작아지고 훨씬 더 빠르게 수렴하여, 빠른 수치적 합산을 가능하게 한다.

오일러 변환은 다음과 같이 일반화될 수 있다.

:$\backslash sum\_\{n=0\}^\backslash infty\; (-1)^n\; \{n+p\backslash choose\; n\}\; a\_n\; =\; \backslash sum\_\{n=0\}^\backslash infty\; (-1)^n\; \{n+p\backslash choose\; n\}\; \backslash frac\{(\backslash Delta^n\; a)\_0\}\{2^\{n+p+1\}\}\; ,$

여기서 p = 0, 1, 2,… 이다.

오일러 변환은 오일러 초 기하 적분 $\backslash ,\_2F\_1$에 적용될 수 있다.

:$\backslash ,\_2F\_1\; (a,b;c;z)\; =\; (1-z)^\{-b\}\; \backslash ,\_2F\_1\; \backslash left(c-a,\; b;\; c;\backslash frac\{z\}\{z-1\}\; \backslash right).$

이항 변환과 오일러 변환은 수의 연분수 표현과 관련이 있다. 이 연분수 표현 $x=[0;a\_1,\; a\_2,\; a\_3,\backslash cdots]$을 갖는다면,

:$\backslash frac\{x\}\{1-x\}=[0;a\_1-1,\; a\_2,\; a\_3,\backslash cdots]$

:$\backslash frac\{x\}\{1+x\}=[0;a\_1+1,\; a\_2,\; a\_3,\backslash cdots].$

3. 공식화

오일러 변환은 수열 $\backslash \{a\_n\backslash \}$에 이항 변환 $\backslash Delta^n$을 적용하여 다음과 같이 정의한다.

:$E\_a\; =\; \backslash sum\_\{k=0\}^\backslash infty\; \backslash frac\{\backslash Delta^k\; a\_0\}\{2^\{k+1\}\}$

만약 급수 $\backslash sum\_\{k=0\}^\backslash infty\; (-1)^k\; a\_k$가 수렴하면, 오일러 변환 $E\_a$도 역시 수렴하고, $\backslash sum\_\{k=0\}^\backslash infty\; (-1)^k\; a\_k\; =\; E\_a$가 성립한다. 즉, 교대급수 판정법에 의해 $\backslash \{a\_n\backslash \}$이 0으로 수렴하는 감소수열이기만 하면 오일러 변환은 수렴하고, 위 정리를 이용할 수 있다.

4. 성질

오일러 변환은 수열의 생성함수와 연분수 표현에 관련된 여러 성질을 가진다.

* 생성함수와의 관계: 수열 \(\{a_n\}\)의 일반 생성함수를 \(f(x)\), 이항 변환된 수열 \(\{s_n\}\)의 일반 생성함수를 \(g(x)\)라 하면, \(g(x) = \frac{1}{1-x} f\left(\frac{-x}{1-x}\right)\) 관계가 성립한다. 지수적 생성 함수의 경우, \(\overline{g}(x) = e^x \overline{f}(-x)\) 관계가 성립한다.
* 연분수와의 관계: 0과 1 사이의 실수 x가 \([0;a_1, a_2, a_3,\cdots]\)와 같은 연분수 표현을 갖는다면, \(\frac{x}{1-x}=[0;a_1-1, a_2, a_3,\cdots]\) 이고 \(\frac{x}{1+x}=[0;a_1+1, a_2, a_3,\cdots]\)이다.

4.1. 생성함수와의 관계

수열 \(\{a_n\}\)의 일반 생성함수를 \(f(x)\), 이항 변환된 수열 \(\{s_n\}\)의 일반 생성함수를 \(g(x)\)라 하면, 다음 관계가 성립한다.

:$g(x)\; =\; \backslash frac\{1\}\{1-x\}\; f\backslash left(\backslash frac\{-x\}\{1-x\}\backslash right).$

지수적 생성 함수의 경우, 다음 관계가 성립한다.

:$\backslash overline\{g\}(x)\; =\; e^x\; \backslash overline\{f\}(-x).$

4.2. 연분수와의 관계

0과 1 사이의 실수 x가 다음과 같은 연분수 표현을 갖는다고 하자.

:$x=[0;a\_1,\; a\_2,\; a\_3,\backslash cdots]$

그러면 다음이 성립한다.

:$\backslash frac\{x\}\{1-x\}=[0;a\_1-1,\; a\_2,\; a\_3,\backslash cdots]$

:$\backslash frac\{x\}\{1+x\}=[0;a\_1+1,\; a\_2,\; a\_3,\backslash cdots].$

5. 응용

오일러 변환은 고전적인 교대급수 \(\sum_{k=0}^\infty (-1)^k \frac{1}{1+k}\)의 값을 구하는 데 응용될 수 있다.

수열 \(a_n = \frac{1}{1+n}\)에 이항 변환을 적용하면 \(\Delta^n a_0 = \frac{1}{n+1}\)이 된다. 이는 파스칼 삼각형과 유사한 도식을 통해 귀납적으로 확인할 수 있다. 그 결과는 다음과 같다.

따라서, \(a_n\)의 오일러 변환은 다음과 같다.

:\(E_a = \sum_{k=0}^\infty \frac{\Delta^k a_0}{2^{k+1}} = \sum_{k=0}^\infty \frac{1}{(k+1)2^{k+1}}\)

위 식의 우변은 \(\log 2\)가 된다.

5.1. 교대급수의 수렴 가속

오일러 변환은 교대급수의 수렴을 가속화하는 데 사용된다. 다음 등식이 성립한다.

:$\backslash sum\_\{n=0\}^\backslash infty\; (-1)^n\; a\_n\; =\; \backslash sum\_\{n=0\}^\backslash infty\; (-1)^n\; \backslash frac\{(\backslash Delta^n\; a)\_0\}\{2^\{n+1\}\}$

위 공식에 x = 1/2를 대입하면, 우변의 항들은 일반적으로 훨씬 더 작아지고 훨씬 더 빠르게 수렴하여, 빠른 수치적 합산을 가능하게 한다.

5.2. 초 기하 급수

오일러 변환은 오일러 초 기하 적분 $\backslash ,\_2F\_1$에 적용될 수 있으며, 이 경우 다음과 같은 형태를 취한다.

:$\backslash ,\_2F\_1\; (a,b;c;z)\; =\; (1-z)^\{-b\}\; \backslash ,\_2F\_1\; \backslash left(c-a,\; b;\; c;\backslash frac\{z\}\{z-1\}\; \backslash right).$

6. 일반화

이항 변환을 함수 $\backslash mathfrak\; J(a)\_n=b\_n$로 정의하면, 이는 다음과 같이 표현할 수 있다.

:$\backslash sum\_\{i=0\}^n(-1)^\{n-i\}\backslash binom\{n\}\{i\}a\_i=b\_n.$

새로운 전방 차분 표를 만들고 각 행의 첫 번째 요소를 가져와 새로운 수열 $\backslash \{b\_n\backslash \}$을 구성하면, 원래 수열의 두 번째 이항 변환은 다음과 같다.

:$\backslash mathfrak\; J^2(a)\_n=\backslash sum\_\{i=0\}^n(-2)^\{n-i\}\backslash binom\{n\}\{i\}a\_i.$

이 과정을 k번 반복하면 다음이 성립한다.

:$\backslash mathfrak\; J^k(a)\_n=b\_n=\backslash sum\_\{i=0\}^n(-k)^\{n-i\}\backslash binom\{n\}\{i\}a\_i.$

이에 대한 역변환은 다음과 같다.

:$\backslash mathfrak\; J^\{-k\}(b)\_n=a\_n=\backslash sum\_\{i=0\}^nk^\{n-i\}\backslash binom\{n\}\{i\}b\_i.$

이를 시프트 연산자 $\backslash mathbf\; E$를 사용하여 일반화하면 다음과 같이 표현할 수 있다.

:$\backslash mathfrak\; J^k(a)\_n=b\_n=(\backslash mathbf\; E-k)^na\_0$

:$\backslash mathfrak\; J^\{-k\}(b)\_n=a\_n=(\backslash mathbf\; E+k)^nb\_0.$

6.1. k-이항 변환

상승 k-이항 변환은 때때로 다음과 같이 정의된다.

:$\backslash sum\_\{j=0\}^n\; \{n\backslash choose\; j\}\; j^k\; a\_j.$

하강 k-이항 변환은 다음과 같다.

:$\backslash sum\_\{j=0\}^n\; \{n\backslash choose\; j\}\; j^\{n-k\}\; a\_j.$

두 변환 모두 수열의 행켈 변환의 커널의 준동형 사상이다.

6.2. 일반화된 이항 변환

프로딩거(Prodinger)는 다음과 관련된 모듈러 형식 변환을 제시한다.

:$u\_n\; =\; \backslash sum\_\{k=0\}^n\; \{n\backslash choose\; k\}\; a^k\; (-c)^\{n-k\}\; b\_k$

이는 다음을 제공한다.

:$U(x)\; =\; \backslash frac\{1\}\{cx+1\}\; B\backslash left(\backslash frac\{ax\}\{cx+1\}\backslash right)$

여기서 U와 B는 각각 수열 $\backslash \{u\_n\backslash \}$과 $\backslash \{b\_n\backslash \}$과 관련된 일반 생성 함수이다.

상승 k-이항 변환은 때때로 다음과 같이 정의된다.

:$\backslash sum\_\{j=0\}^n\; \{n\backslash choose\; j\}\; j^k\; a\_j.$

하강 k-이항 변환은 다음과 같다.

:$\backslash sum\_\{j=0\}^n\; \{n\backslash choose\; j\}\; j^\{n-k\}\; a\_j$.

둘 다 수열의 행켈 변환의 커널의 준동형 사상이다.

이항 변환이 다음과 같이 정의되는 경우:

:$\backslash sum\_\{i=0\}^n(-1)^\{n-i\}\backslash binom\{n\}\{i\}a\_i=b\_n.$

이를 함수 $\backslash mathfrak\; J(a)\_n=b\_n$과 같다고 하자.

새로운 전방 차분 표를 만들고 이 표의 각 행의 첫 번째 요소를 가져와서 새로운 수열 $\backslash \{b\_n\backslash \}$을 구성하면, 원래 수열의 두 번째 이항 변환은 다음과 같다.

:$\backslash mathfrak\; J^2(a)\_n=\backslash sum\_\{i=0\}^n(-2)^\{n-i\}\backslash binom\{n\}\{i\}a\_i.$

동일한 과정을 k번 반복하면 다음이 성립한다.

:$\backslash mathfrak\; J^k(a)\_n=b\_n=\backslash sum\_\{i=0\}^n(-k)^\{n-i\}\backslash binom\{n\}\{i\}a\_i.$

역변환은 다음과 같다.

:$\backslash mathfrak\; J^\{-k\}(b)\_n=a\_n=\backslash sum\_\{i=0\}^nk^\{n-i\}\backslash binom\{n\}\{i\}b\_i.$

이는 다음과 같이 일반화할 수 있다.

:$\backslash mathfrak\; J^k(a)\_n=b\_n=(\backslash mathbf\; E-k)^na\_0$

여기서 $\backslash mathbf\; E$는 시프트 연산자이다.

역변환은 다음과 같다.

:$\backslash mathfrak\; J^\{-k\}(b)\_n=a\_n=(\backslash mathbf\; E+k)^nb\_0.$

7. 이항 컨볼루션

두 복소수 수열 $\{a_n\}$, $\{b_n\}$ ($n=0,1,2,\ldots$)의 이항 컨볼루션은 다음과 같이 정의된다.

: $(a\circ b)_n=\sum_{k=0}^n{n \choose k}a_k b_{n-k},\ \ n=0,1,2,\ldots$

이 컨볼루션은 결합 법칙과 교환 법칙이 성립하며, 수열 $\{e_n\}$ ($e_0=1$이고 $n=1,2,\ldots$에 대해 $e_n=0$)은 이항 컨볼루션에서 항등원 역할을 한다. $a_0 \ne 0$인 수열 $\{a_n\}$은 역원을 가지며, 이러한 수열들의 집합은 이항 컨볼루션 하에서 아벨 군을 형성한다.

이항 컨볼루션은 지수 생성 함수의 곱에서 나타난다.

: $\left( \sum^\infty_{n=0} a_n {x^n \over n!} \right)
\left( \sum^\infty_{n=0} b_n {x^n \over n!} \right) =
\sum^\infty_{n=0} (a\circ b)_n {x^n \over n!}.$

이항 변환은 이항 컨볼루션으로 표현 가능하다. 모든 $n$에 대해 $\lambda_n=(-1)^n$이고 $1_n=1$일 때, 다음과 같이 표현된다.

: $(Ta)_n=(\lambda a\circ 1)_n.$

다음 공식은 뫼비우스 반전과 유사하다.

: $t_n = \sum_{k=0}^n (-1)^{n-k} {n\choose k} a_k
\iff a_n=\sum_{k=0}^n {n\choose k} t_k$

이는 $t_n = (a\circ \lambda)_n
\iff a_n=(t\circ 1)_n$으로 표현되는데, $\lambda_n$이 이항 컨볼루션에서 $1_n$의 역원이기 때문이다.

산술 함수 $f$와 $g$의 이항 컨볼루션은 다음과 같이 정의된다.

: $(f\circ_B g)(n)=\sum_{d\mid n} \left( \prod_p
\binom{\nu_p(n)}{\nu_p(d)} \right) f(d)g(n/d),$

여기서 $n=\prod_p p^{\nu_p(n)}$는 양의 정수 $n$의 표준 소인수분해이고, $\binom{\nu_p(n)}{\nu_p(d)}$는 이항 계수이다.

8. 적분 표현

시퀀스가 복소해석 함수에 의해 보간될 수 있을 때, 시퀀스의 이항 변환은 보간 함수에 대한 뇌를룬-라이스 적분을 통해 표현될 수 있다.