아래 누가 게속 카탈란 물어보길래 중고딩 과정에서 생각해보는데 조합론적으로 카탈란 원래 일반항 + 점화식 한방에 유도하는거 말고 방법이 생각이 안남


점화식이 재귀적인데 변변 곱하는 컨볼루션 형태로 정의되있어서 고딩 수준에서 바로 풀 방법이 있음?

생성함수 두고서 c(x)=1+xc(x)^2 놓고서 구하고 초항 만족하는거 찾아서 최종 급수전개 -> 이렇게 구할수는 있음. 근데 생성함수는 그냥 경시나 대학 이산수학 과정 가는거나 다름없고. 고딩 수준에서 이거 구할려면 점화식에서 재귀적으로 곱해진거 풀어야 되는데 그러면 다음 셋 중 하나를 해야됨


1. 미리 일반항을 알고 있고 그걸 가지고 귀납법으로 때려맞추면서 게산 노가다로 확인

2. 걍 점화식으로 -> 카탈란수 나오는 격자문제로 바꾸고 -> 조합론적으로 동일하니 이거다 하고 답 구함

3. 아니면 그냥 무슨 신묘한 기법으로 점화식을 풀어내야됨


이걸 3번으로 하는 방법이 있음? 1번이라고 해도 개노가다 계산을 해야될거 같고 실상 2번이 유일한 방법 아님?