強數學歸納
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為起始數字
:
: 但想不出好的證明方式
:
: 請大大指教，謝謝!
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 67.188.83.255
: ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1459471026.A.184.html
: 推 FRAXIS: 我猜 induction 04/01 08:56
: 推 ckc1ark: 假設n個人 分兩堆x+y後 兩堆人互握(共會有x*y次) x和y再 04/01 21:31
: → ckc1ark: 繼續做下去 這樣的行為會讓每個人都握到其他所有的人 所 04/01 21:31
: → ckc1ark: 以握手的總次數是n*(n-1)/2 04/01 21:31
: → ckc1ark: 或是說任兩個人只在被分成不同堆時會互握到一次 04/01 21:32
: 推 LPH66: induction (數學歸納法) 無誤 04/01 21:40
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.25.12.210
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1460812646.A.F37.html