$$f(x,y)=f(y,x)$$ 와 같이 두 변수 \(x\) 와 \(y\)를 서로 교환해도 식의 값이 변하지 않는 식을 대칭식이라고 합니다. \(x^n+y^n\)은 대표적인 2변수 대칭식 중 하나로, 그 값을 구하는 문제가 자주 출제 됩니다. 이 식의 값은 다음과 같은 귀납적 관계(점화식)을 이용하면 그 값을 고속으로 계산할 수 있습니다.
$$x^{n+2}+y^{n+2}=(x+y)(x^{n+1}+y^{n+1})-xy(x^n+y^n), n\ge 1\qquad(1)$$
이 글에서는 이 점화식을 사용한 \(x^n+y^n\)의 계산법과 그 응용을 설명합니다.
\(x^n+y^n\) 의 점화식이 필요한 이유
보통 참고서나 문제집에서는 $$x^2+y^2=(x+y)^2-2xy$$$$x^3+y^3=(x+y)^3-3xy(x+y)$$과 같은 방법으로 식의 변형을 통해 식의 값을 계산하는 방법을 소개하고 있습니다. 하지만 $$(x^{5}+y^{5})+(x^{6}+y^{6})+(x^{7}+y^{7})$$ 과 같은 문제에서 \(x^5+y^5\), \(x^6+y^6\), \(x^7+y^7\) 의 식을 하나 하나씩 변형해서 일일이 구해주려면 꽤 귀찮은 작업이 되어버립니다. 이때에는 앞서 설명한 \(x^n+y^n\)의 점화식을 사용하면 각 대칭식을 일일이 변형하지 않고도 빠르게 구할 수 있습니다.
점화식의 사용법
이 점화식(1)의 좌변을 보면 \(n\)과 관계없이 \(x+y\)와 \(xy\)가 사용되고 있습니다. 따라서 이 점화식을 사용하려면 \(x+y\) 와 \(xy\)의 값을 미리 알고 있어야 합니다. 만약 점화식(1)에 \(n=1\)을 대입하면 $$x^3+y^3=(x+y)(x^2+y^2)-xy(x+y)$$를 얻을 수 있습니다. 즉 점화식(1)에 \(n=1,\ 2,\ 3,…\) 을 대입하여 그 값을 계산할 수 있는 식은 \(x^3+y^3,\ x^4+y^4,\ x^5+y^5…\) 입니다. 또한 좌변에 있는 \(x^2+y^2\) 은 점화식의 결과가 아니므로 이 식의 값 역시 변형$$(x+y)^2=(x+y)^2-2xy$$를 이용하여 다른 식의 값을 구하기 전에 미리 구해 놓아야 합니다.
예: \(x+y=2,\ xy=-1\) 일 때 \(x^n+y^n\) 구하기
$$T_n=x^n+y^n$$으로 정의하고, $$x+y=2,\ xy=-1$$ 이라 하면, $$\begin{align}T_{n+2}=x^{n+2}+y^{n+2}&=(x+y)(x^{n+1}+y^{n+1})-xy(x^n+y^n)\\&=2T_{n+1}-(-1)T_n\\&=2T_{n+1}+T_n\end{align}$$이 됩니다.따라서$$\begin{align}T_1&=x+y=2\\
T_2&=x^2+y^2=(x+y)^2-2xy=2^2-2(-1)=4+2=6\end{align}$$ 로 구해놓으면 점화식을 기계적으로 반복해서 적용하면 \(T_3,\ T_4,\ T_5,…\)의 값을 구할 수 있습니다.$$\begin{align}T_3&=x^3+y^3=2T_2+T_1=2\cdot 6+2= 14\\
T_4&=x^4+y^4=2T_3+T_2=2\cdot 14 + 6= 34\\
T_5&=x^5+y^5=2T_4+T_3=2\cdot 34 + 14=82\\
T_6&=x^6+y^6=2T_5+T_4=2\cdot 82 + 34=198\\
T_7&=x^7+y^7=2T_6+T_5=2\cdot 198+82= 478\end{align}$$
응용 : \(x^n+\frac{1}{x^n}\) 의 값 구하기
이 점화식은 \(x^n+\frac{1}{x^n}\) 의 값을 구하는데에도 사용 할 수 있습니다. $$S_n=x^n+\frac{1}{x^n}=x^n+\left(\frac{1}{x}\right)^n$$이라 하고, 점화식을 적용하면, $$\require{cancel}\begin{align}S_{n+2}&=x^{n+2}+\left(\frac{1}{x}\right)^{n+2}\\&=\left(x+\frac{1}{x}\right)\left(x^{n+1}+\left(\frac{1}{x}\right)^{n+1}\right)-\cancel{x}\cdot\frac{1}{\cancel{x}}\left(x^n+\frac{1}{x^n}\right)\\&=\left(x+\frac{1}{x}\right)S_{n+1}-S_n\qquad(2)\end{align}$$ 이 됩니다.
예:\(x+\frac{1}{x}=2\) 일 때, \(x^n+\frac{1}{x^n}\) 구하기
예를 들어 $$x+\frac{1}{x}=2$$ 라고 하면 이것을 식(2)에 대입하면 $$S_{n+2}=\left(x+\frac{1}{x}\right)S_{n+1}-S_n=2S_{n+1}-S_n$$이 됩니다. 따라서 $$\begin{align}S_1&=x+\frac{1}{x}=2\\S_2&=x^2+\frac{1}{x^2}=(x+\frac{1}{x})^2-2=2^2-2=2\end{align}$$ 로 구해 놓으면 \(S_3,\ S_4,\ S_5…\)는 이 점화식을 반복하여 적용하는 것으로 구할 수 있습니다. $$\begin{align}S_3&=2S_2-S_1=2\cdot 2-2=2\\
S_4&=2S_3-S_2=2\cdot 2-2=2\\
S_5&=2S_4-S_3=2\cdot 2-2=2\\
…\\
S_n&=2\end{align}$$