[離散] strictly increasing sequence的規則

[mqazz1 (無法顯示)]

http://small.lib.nccu.edu.tw/exam/data/master/cs/cs89.pdf

想請教第一題的(b)小題

let A(n), (n>=2) be the number of strictly increasing sequence of positive
integers that have 1 as the first term and n as the last term

that is, sequences x(1), x(2), ..., x(k)
where x(1)=1 and x(k)=n and x(j)<x(j+1) for 1<=j<k

(b) find a recurrence relation for A(n) (n>1)

===========================================================================

我有地方看不太懂

當n>=3時，考慮第一項為1，最後一項為n的strictly increasing sequence中，
討論倒數第二項

        若倒數第二項為n-1，則相當於第一項為1，最後一項為n-1的
        stricly increasing sequence，有A(n-1)種

        若倒數第二項為n-2，則相當於第一項為1，最後一項為n-2的
        stricly increasing sequence，有A(n-2)種

        若倒數第二項為  2，則相當於第一項為1，最後一項為  2的
        stricly increasing sequence，有A(2)種

        再加上1,n這個strictly increasing sequence

所以A(n) = A(n-1) + A(n-2) + ... + A(2) + 1


請問會什麼最後會變到 A(n) = 2A(n-1) ?


謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.228.24.138
→ Vulpix      :因為 A(n-2) + ... + A(2) + 1 = A(n-1)