數列關係的證明
Consider the following series:\(1,2,3,4,5,10,20,40,\ldots,\)which starts as an arithmetic series, but after the first 5 terms becomes a geometric series. Prove that any positive integer can be written as a sum of distinct numbers from this series.Find an expression for the sum of the \(i-\)th row of the following triangle, and prove the correctness of your claim. Each entry in the triangle is the sum of three entries directly above it(a nonexisting entry is considered 0).
\(\matrix{&&&&1&&&&\cr &&&1&1&1&&&\cr&&1&2&3&2&1&&\cr&1&3&6&7&6&3&1&\cr 1&4&10&16&19&16&10&4&1}\)
請各位老師 幫忙 謝謝
回復 1# P78961118 的帖子
第 1 題：此數列 \(1,2,3,4,5,10,20,40,80, \cdots\)
其實就是 \(1, 2, 3, 4\) 以及剩下的 \(5\cdot 2^0 , 5\cdot 2^1, 5\cdot 2^2, 5\cdot 2^3, 5\cdot 2^4, \cdots\)
對任意正整數 \(M\) ，被 \(5\) 除之後，假設餘數為 \(r\)，則 \(r\in\left\{0,1,2,3,4\right\}\)，
可將商以唯一的二進位表示法寫為 \(a_n2^n + a_{n-1}2^{n-1} +\cdots + a_1\cdot2 + a_0\)
其中 \(n\) 為非負數整數，\(a_n, a_{n-1}, a_{n-2}, \cdots, a_1, a_0 \in\left\{0,1\right\}\)
且 \(r, a_n, a_{n-1}, a_{n-2}, ..., a_1, a_0\) 不全為零，
亦即
\(M =\) 除數 * 商 + 餘數
\(= 5\left(a_n2^n + a_{n-1}2^{n-1} + \cdots + a_1\cdot2 + a_0\right) + r\)
\(= a_n\cdot5\cdot2^n + a_{n-1}\cdot5\cdot2^{n-1} + \cdots + a_1\cdot5\cdot2 + a_0\cdot5 + r\)
若 \(r\neq0\)，則 \(r\) 為此數列的前四項之中的一個，
若 \(r=0\) 則沒有取前四項之一，
若 \(a_i=1\) ，則表示有加上 \(5\cdot2^i\) (這個數字是此數列中的第 \(i+5\) 項)
若 \(a_i=0\) ，則表示沒有加上 \(5\cdot2^i\) (這個數字是此數列中的第 \(i+5\) 項)
回復 1# P78961118 的帖子
第一題試試看數學歸納法，\(n\in N\)\(n\in (0,10]\) 時皆成立！(6=5+1, 7=5+2, 8=5+3, 9=5+4)
設 \(n\in [10,10\times 2^k)\)，其中定數 \(k\in N\) ， 均可被表成此數列中的相異數和
當 \(n\in [10\times 2^k, 10\times 2^{k+1})\) 時，\(n=10\times 2^k + (n-10\times 2^k)\)
而 \((n-10\times 2^k)\in [0,10\times 2^k)\) ，由歸納假設條件可知，此數可被表成此數列中的相異數和
由數學歸納法，得證！
回復 1# P78961118 的帖子
第 2 題：對於非負整數 \(i\)，第 \(i+1\) 列的數字即為 \(\displaystyle (x^2+x+1)^i\) 以 \(x\) 的升冪排列之後的係數。
以數學歸納法證明之。
1. 當 \(i=0\) 時， \(\displaystyle \left(x^2+x+1\right)^0=1\) 為第 \(1\) 列的數字，成立。
2. 假設當 \(i=k\) 時，\(\displaystyle \left(x^2+x+1\right)^k=\sum_{t=0}^{2k}a_t x^t\)
其中 \(<a_t>_{t=0}^{2k}\) 為題述第 \(k\) 列數字的數列，
則當 \(i=k+1\) 時，
\(\displaystyle \left(x^2+x+1\right)^{k+1}=\left(\sum_{t=0}^{2k}a_t x^t\right)\left(x^2+x+1\right)\)
\(\displaystyle =\sum_{t=0}^{2k}a_t x^{t+2}+\sum_{t=0}^{2k}a_t x^{t+1}+\sum_{t=0}^{2k}a_t x^t\)
\(\displaystyle =\sum_{t=2}^{2k+2}a_{t-2} x^t+\sum_{t=1}^{2k+1}a_{t-1} x^t+\sum_{t=0}^{2k}a_t x^t\)
\(\displaystyle =\left(a_{2k-1}x^{2k+1}+a_{2k}x^{2k+2}+\sum_{t=2}^{2k}a_{t-2} x^t\right)+\left(a_0x+a_{2k}x^{2k+1}+\sum_{t=2}^{2k}a_{t-1} x^t\right)+\left(a_0+a_1x+\sum_{t=2}^{2k}a_t x^t\right)\)
\(\displaystyle =a_0+\left(a_0+a_1\right)x+\sum_{t=2}^{2k}\left(a_{t-2}+a_{t-1}+a_t\right)x^t+\left(a_{2k-1}+a_{2k}\right)x^{2k+1}+a_{2k}x^{2k+2}\)
依照題述規律，可知 \(\displaystyle \left(x^2+x+1\right)^{k+1}\) 以 \(x\) 的升冪排列之後的係數亦為題述第 \(k+1\) 列數字的數列，亦成立。
由 1. & 2. 及數學歸納法原理，可知對於任意非負整數 \(i\)，第 \(i+1\) 列的數字即為 \(\displaystyle (x^2+x+1)^i\) 以 \(x\) 的升冪排列之後的係數。
因此，將 \(x=1\) 帶入 \(\displaystyle (x^2+x+1)^i\) 即可得第 \(i+1\) 列的數字和為 \(3^i\) 。 請問瑋岳老師 怎麼知道是(x^2+x+1)^i 以 x 的升冪排列之後的係數
回復 5# P78961118 的帖子
觀察前後列規律而得。頁:
[1]