[問題] 分堆問題 證明

[sorryla (Mr.東)]

最近小遇到一個問題，想不出證明方式，所以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
推 ckc1ark: 假設n個人 分兩堆x+y後 兩堆人互握(共會有x*y次)  x和y再
→ ckc1ark: 繼續做下去 這樣的行為會讓每個人都握到其他所有的人 所
→ ckc1ark: 以握手的總次數是n*(n-1)/2
→ ckc1ark: 或是說任兩個人只在被分成不同堆時會互握到一次
推 LPH66: induction (數學歸納法) 無誤