엄격한 2 진 트리의 나뭇잎 수

파생을 찾고 있는데 어떻게 결과를 얻었습니까?엄격한 2 진 트리의 나뭇잎 수

i의 힘에 2의 합계, i가 0에서 n => (n + 1) -1의 2 승으로 주어진다.

위의 결과를 얻은 방법이나 해결책이있는 적절한 링크를 보여줄 수 있습니까?

감사합니다.

유도에 의한 증명 : n = 0, 2^0 = 1 = 2^1 - 1 인 경우 n = k-1, 2^0 + ... + 2^k = 2^0 필요에 따라 + ... + 2^(k-1) + 2^k = (2^k-1) + 2^k = 2 * 2^k-1 = 2^(k + 1) –

실제로 그 수는 잎이 아니라 노드 수입니다. –

증명을 읽을 수 있습니다.

그것이 N 마찬가지의 관찰 = 0 - sum0-> 0 = 1 = 2^1 - 1

마찬가지 가정 N = K-1이므로이 합계 [0-> K-1] = 2^0-> k] = sum [0-> k-1] + 2^k = 2^k-1 + 2^k = 2 (2^k) -1 = 2^(k + 1) - 1

따라서 모든 n에 대해 참이다.

2011-08-08 12:20:16 Chowlett

수학에서 나온 것은 geometric progression입니다. 당신이 명확하게 (직관적) 설명을 원하는 경우

, 당신은 유도에 의한 this nice explanation

2011-08-08 12:18:28 Fezvez

답변