retagged by
662 views
2 votes
2 votes
Given a integer N greater than zero.

How many sequences of 1's and 2's are there such that sum of the numbers in the sequence = N ?

(not necessary that every sequence must contain both 1 and 2 )

example :

for N = 2 ; 11,2 => ans = 2 sequences of 1's and 2's

for N = 3 ; 11,12,21 => ans = 3 sequences of 1's and 2's
retagged by

2 Answers

Best answer
1 votes
1 votes
Let T(n) be the number of possible sequences of 1's and 2's having sum 'n',

Now we will divide these sequences into 2 cases: Sequences starting with 1 and starting with 2.

if a sequence of 1's and 2's having sum 'n' starts with 1 then, our problem reduces to finding the sequences of 1's and 2's with sum n-1, which is T(n-1).

similarly, if a sequence starts with 2, our problem reduces to T(n-2).

Hence T(n)= T(n-1) + T(n-2), where T(1)=1, T(2)=2.
selected by
3 votes
3 votes

It is (N+1)th fibonacci number.

Observe the pattern: http://ideone.com/QLb1CZ

Related questions

17 votes
17 votes
2 answers
2
minal asked Nov 24, 2016
2,843 views
How many positive integers less than 1,000,000 have the sum of their digits equal to 19? (using generating function)
0 votes
0 votes
0 answers
3
codingo1234 asked Dec 10, 2018
304 views
Difference between getting closed form of generating function and closed form of the given sequence ,pls someone explain with an example