強數學歸納
step 1: 證明 n=1,2 成立
n=1, 顯然成立
n=2, 2=1+1 成立
step 2: 假設n<k時命題成立，接著考慮n=k
把 k 拆成 k=x+y 時， x<n 且 y<n
x 可得到總和 x(x-1)/2
y 可得到總和 y(y-1)/2
再加上 x*y
可得 x(x-1)/2 + y(y-1)/2 + x*y
= (x*x-x+y*y-y+2*x*y)/2
= ( (x*x+2*x*y+y*y) - (x+y) )/2
= ( (x+y)*(x+y) - ( x+y ) ) / 2
= (x+y)( (x+y) - 1 ) /2
= k * ( k - 1 ) /2
得證
※ 引述《sorryla (Mr.東)》之銘言：
: 標題: [問題] 分堆問題 證明
: 時間: Fri Apr 1 08:37:04 2016
:
: 最近小遇到一個問題，想不出證明方式，所以PO文請大大們求救
:
: 問題:
:
: 起始給一個數字，然後每次都將數字分成兩堆，然後將這兩堆的乘積加起來
: 直到最後每一堆都剩下1為止，這總和會是一個常數
:
: 例子:
:
: 起始為5:
:
: 我們可以有以下幾種可能分法:
:
: 5 5
: / \ / \
: 2 3 2*3 = 6 1 4 1*4 = 4
: /\ /\ / \
: 11 2 1 1*1 +2*1 = 3 2 2 2*2 = 4
: /\ /\ /\
: 1 1 1*1 = 1 1 1 1 1 1*1 + 1*1 = 2
:
: 6 + 3 + 1 = 10 4 + 4 + 2 = 10
:
: 這兩總分法最後的總和都是10
:
: 我知道這個常數為N*(N - 1) / 2，N為起始數字
:
: 但想不出好的證明方式
:
: 請大大指教，謝謝!
:
: