아래 세특 어쩌구저쩌구 보라고 올린거
보기 힘들게 썼으니 알아서 봐라


1.생성함수
생성함수는 하나의 수열을 함수로 대응시킨 거임

예를들어
1, 1, 1, 1, 0, 0, 0,.....이런 식의 수의 나열을
함수로 표현한다면

첫번째는 1 두번째도 1 세번째도 1 네번째도 1
그 이후는 0이니
f(x)=(1×x+1×x^2+1×x^3+1×x^4+0×x^5+.....)
로 나태낼 수 있고

1, 1, 1, 1, 0, 0, 0,.....은
f(x)=x+x^2+x^3+x^4에 대응됨

일반화 시켜서
n번째의 값이 f(n)의 값을 갖는 수열은
G(x)=f(0)x^0+f(1)x^1+.....꼴인
생성함수 G(x)꼴을 갖는다 말 할 수 있음

f(n)x^n은 수열의 n번째 값이 f(n)인데
f(0)x^0의 값이 뭐냐 물어볼수 잇는데

이건 수열을 0번째부터 시작할지말지 문제임
수열이 1번째부터 시작하면 f(0)=0으로 두면 됨



2.피보나치 수열

f(n)=f(n-1)+f(n-2), f(1)=1,f(2)=1를 만족하는
수열을 피보나치라고 함

이 수열의 생성함수 G(x)는

G(x)=1x+1x^2+2x^3+3x^4+5x^5....
이런식으로 표현 됨

G(x)=f(1)x+f(2)x^2+f(3)x^3+...
=f(1)x+f(2)x^2+(f(1)+f(2))x^3+(f(2)+f(3))x^4...
를 적절히 쪼개면

f(1)x+f(2)x^2랑
f(1)x^3+f(2)x^4+...랑
f(2)x^3+f(3)x^4+.....로 쪼개짐

f(2)x^2=f(1)x^2니까
A=f(1)x랑
B=f(1)x^3+f(2)x^4+...랑
C=f(1)x^2+f(2)x^3+f(3)x^4+.....로
쪼개진다고 다시 볼 수 있음

A=x
B=x^2(f(1)x+f(2)x^2+...)=x^2G(x)
C=x(f(1)x+f(2)x^2....)=xG(x)
로 다시 표현되고

G(x)=A+B+C=x+xG(x)+x^2G(x)는
G(x)=x/(1-x-x^2)으로 표현 됨


따라서 우리는 이런 결과를 얻을 수 있음

피보나치 수열의 생성함수
x+x^2+2x^3+3x^4+...=x/(1-x-x^2)로 표현되고
우변인 x/(1-x-x^2)를 부분분수 전개해서

x/(1-x-x^2)=C_1/(1-ax)+C_2/(1-bx)꼴로 나타낼 수 있고

1/(1-x)=1+x+x^2+x^3+...의 성질을 이용한다면

x/(1-x-x^2)의 n번째 항은 C_1×(ax)^n+C_2×(bx)^n으로 나타낼 수 있고

C_1×a^n+C_2×b^n이 피보나치수열의 n번째 수가 되는거임

여기서 a,b는 x/(1-x-x^2)의 부분분수를 푼거니
반드시 1-x-x^2의 해고 1-x-x^2는 피보나치의 특성방정식임

임의의 선형점화식
f(n)=Af(n-1)+Bf(n-2)+Cf(n-3)꼴 만들고
위 과정 똑같이 해보면
특성점화식이 중근을 갖지 않을 때
특성방정식의 해가 a b c를 갖는다면
f(n)=C_1×a^n+C_2×b^n+C_3×c^n
꼴로 나타남을 확인 할 수 있을거임



3.중근

선형점화식의 생성함수 G(x)의
부분분수를 풀어서 점화식을 푸는데

G(x)=1/(1-x)^2+1/(1-2x)처럼
중근을 갖는 경우가 있음

1/(1-x)^2=(1+x+x^2....)(1+x+x^2....)의 꼴이고
x^n의 계수는 x^0×x^n부터 x^n×x^0의 계수를 다 더한거임

따라서 n을 적절히 쪼개서
0+n=1+(n-1)=..=n+0로 만드는 경우의 수고

똑같은 공이 무한개가 든 두개의 상자에서
총 n개의 공을 뽑는 가지수 2Hn을 의미함

1/(1-2x)^2=.... (n+1)C1 ×(2x)^n... 꼴이되고

중근이 있는 경우 (n+1)2^n꼴이 되게 됨








이런 방식으로 생성함수를 구해서 점화식을 푸는거임
특성방정식은 중간 부분분수 싹다 생략한거고

한두개 풀다보면 그냥 피보나치수열의 일반항이
왜 r^n꼴이어야만 하는지는 당연하게 느껴질거임