how to prove $T(n) \le 2^{n-1}$ , $T(n)$ is the number of way that write n as the sum of 1's and 2's

Question

such as n = 3, T(n) =3, because 3 = 1+1+1, 3=1+2 ,3 =2+1.

score 2 · Accepted Answer · answered Feb 21 '13 at 02:05

2

Hint: Notice that since we are counting ordered partitions, and the first term is either $1$ or $2$, we have the recurrence $$T(n+1)=T(n)+T(n-1).$$ From here you could solve the recurrence or use induction.

answered Feb 21 '13 at 02:05

Eric Naslund

72,099

1

As an aside, you need to prove 2 base cases if you are to use induction here. – muzzlator Feb 21 '13 at 02:10

how to prove $T(n) \le 2^{n-1}$ , $T(n)$ is the number of way that write n as the sum of 1's and 2's

1 Answers1