N을 홀수의 합으로 표현하는 방법은 몇 가지입니까? [복제]

Question

몇 가지 기본적인 수학 코딩 문제를 해결하고 있었는데 For any number $N$, 표현하는 방법의 수 $N$ 홀수 합계는 $Fib[N]$ 어디 $Fib$Fibonnaci입니까, 나는 이것에 대한 유효한 증거가 없으며 재발을 사용하여이 문제를 어떻게 해결할 수 있는지 이해하지 못했습니다. 누군가 제공 할 수 있습니까?
만약 당신이 그것을 얻지 못한다면 N = 4라고 가정하자 홀수 숫자의 합은 3이고 Fibonnaci는$3$

$4=> 1+1+1+1$
$4=> 1+3$
$4=> 3+1$
참고-> 구성이 주문됩니다. $( 1+3)$ 과 $(3+1)$다르다 . UPD-> 내가 직접 관찰했다고 주장하지 않지만 문제 해결 방법에서 찾은 결과, 유효한 증거 / 이유를 찾도록 요청했습니다.

Answer 1

의 말을하자 $S(n)$ 작성하는 방법의 집합입니다 $n$ 홀수의 합으로.

이 집합을 두 개의 하위 집합으로 분할 할 수 있습니다. $A(n)$ 과 $B(n)$, 어디 $A(n)$ 마지막 합계가 a 인 합계의 집합입니다. $1$, 및 $B(n)$ 다른 모든 합계의 집합입니다.

이유를 알 수 있습니까 $A(n)$ 크기가 $S(n-1)$? 이유를 알 수 있습니까$B(n)$ 크기가 $S(n-2)$?

이것을 증명하면 $|S(n)| = |A(n)| + |B(n)| = |S(n-1)| + |S(n-2)|$, 이는 피보나치 재발 관계입니다. 그런 다음 귀납법으로 수열이 피보나치 수열과 같다는 것을 증명할 수 있습니다.

Answer 2

우리는 첫 번째 원칙에서 홀수 부분으로의 작곡 수는 다음과 같이 주어집니다.

$$[z^N] \sum_{q\ge 1} \left(\frac{z}{1-z^2}\right)^q.$$

이것은 다음을 단순화합니다.

$$[z^N] \frac{z/(1-z^2)}{1-z/(1-z^2)} = [z^N] \frac{z}{1-z-z^2}.$$

지금 $$F(z) = \frac{z}{1-z-z^2}$$ 피보나치 수의 OGF이고 우리는 주장이 있습니다.