Question

一个人要登上n级台阶,如果他每步可以跨一级或两级,共有多少种方法?

Answer 1

设一级x步,2级y部；则x+2y=n,

1.:n为奇数2k-1 时,x为奇数,y=(n-x)/2,只要从x+y =(n+x)/2步中选出x步走一阶,其余走2阶即可 ,有C((n+x)/2,x)种走法,令x=1,3,5,……,n,再相加即得：

N=C(K,1)+C(K+1,3)+……+C(2k-1,2k-1）；

2.n为偶数2k时,x为偶数,同理,N=C(k,0)+C(K+1,2)+C(K+2,4)+……+C(2k,2k）；