作者Lwms (Uniform is a plus)
看板tutor
標題Re: [解題] 高一數學 組合的證明題
時間Sun Feb 24 11:48:18 2013
※ 引述《ivorycoast ()》之銘言：
: 1.年級：高一
: 2.科目：數學
: 3.章節：排列組合
: 4.題目：
: (1)、試證C(2n，n)可被n+1整除。
: (2)、對任意正整數n、k，其中n大於等於k，
: 求證C(n，k)、C(n+1，k)、C(n+2，k)......、C(n+k，k)
: 的最大公因數為1。
: (3)、設N=19^88-1 (19的88次方減1)，
: 求N的所有形如2^a．3^b的因數總和，
: 其中a，b為正整數。
1. 由 C(n, k) 的定義可知
(n+1) C(2n, n-1)
C(2n, n) = ------------------ , 又因為 C(2n, n), C(2n, n-1) 均為整數
n
所以
n | (n+1) C(2n, n-1), 其中 (n, n+1) = 1 可以推得 n | C(2n, n-1)
C(2n, n-1)
C(2n, n) = (n+1) ------------ 為 n+1 的倍數
n
其中黃色部分 : 若 n | ab 且 (n,a) = 1 則 n | b 可以透過數論證明
或用標準分解式 (質因數分解) 說明
2.
對 k 做數學歸納法
k = 1 時
( C(n,1), C(n+1,1) ) = ( C(n,1), C(n,1)+C(n,0) )
= ( C(n,1), C(n,0) ) = ( n, 1 ) = 1
一般的 k
( C(n,k),
C(n+1,k), ..., C(n+k, k) )
黃色部分用 C(n, k) = C(n-1, k) + C(n-1, k-1) 拆開, C(n-1, k) 恰為前項
根據輾轉相除法原理, 可以減去
= ( C(n,k), C(n, k-1), C(n+1, k-1), ..., C(n+k-1,k-1) )
= ( C(n,k), (C(n, k-1), C(n+1, k-1), ..., C(n+k-1,k-1)) )
根据歸納假設, 後面部分最大公因數為 1
= ( C(n,k), 1) = 1
P.S 輾轉相除法原理: 若 p 為若干數的因數, 則這些若干數互相加減, 亦為 p 的倍數
所以 (a, b) = (a, b - a) 可以推廣至多個數.
--
--
幽默是把橡皮造的劍：容許你刺中要害卻不流血。
Mary Hirsch
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.74.94