puremaths 問題3

(a)
let S(n) be the corresponding statement of part (a)
when k=0
x+2y=0
Obviously, only (0,0) is the solution
n(0)=(0+2)/2=1
S(0) is true
when k=1
x+2y=1
Obviously, only (1,0) is the solution
n(1)=(1+1)/2=1
S(1) is true
Assume that when k<=m-1 S(k) is true
when k=m
if m is odd
then
x+2y=m
x-1+2y=m-1
let x'=x-1
then
x'+2y=m-1
and the no of solutions is equal to n(m-1)=(m+1)/2
since x' and x are 1-1 correspondence
we conclude that the no of solutions of x+2y=m
is also equal to (m+1)/2
if m is even
then
x+2y=m
x-1+2y=m-1
let x'=x-1
then
x'+2y=m-1
and the no of solutions is equal to n(m-1)=(m-1+1)/2=m/2
since x' and x are 1-1 correspondence
However, when x=0, we can find a y=m/2 such that
x+2y=m is true
we conclude that the no of solutions of x+2y=m
is also equal to m/2+1=(m+2)/2
So, S(m) is true
By mathematical induction, for all non-negative values of k
S(k) is true
(b)
To find the no of non-negative solutions of x+2y<=p
let N(P) represents the no of non-negative solutions of x+2y<=p
then
N(P)
=Σ n(k) [k from 0 to p]
=n(0)+n(1)+...+n(p)
=2/2+2/2+4/2+4/2+...+n(p)
if p is odd
n(p)=(p+1)/2
N(P)
=2/2+2/2+4/2+4/2+...+(p+1)/2+(p+1)/2
=2[2/2+4/2+...+(p+1)/2]
=[2+4+...+(p+1)]
=[(p+1)/4][2*2+[(p+1)/2-1]*2]
=[(p+1)/4][4+p-1]
=[(p+1)][p+3]/4
if p is even
n(p)=(p+2)/2
N(P)
=2/2+2/2+4/2+4/2+...+(p)/2+(p)/2+(p+2)/2
=2[2/2+4/2+...+(p)/2]+(p+2)/2
=[2+4+...+(p)]+(p+2)/2
=[(p)/4][2*2+[(p)/2-1]*2]+(p+2)/2
=[(p)/4][4+p-2]
=[(p)][p+2]/4+(p+2)/2
=[(p)][p+2]/4+2(p+2)/4
=(p+2)(p+2)/4
=(p+2)^2/4




2006-12-28 03:19:42 補充：
非常有趣的問題