Question

Let L = {a, bb}
How many strings of length 10 are present in L* ?

Answer 1

Length 1: only one string - "a"

Length 2: "aa", "bb" - 2 strings

Length 3: "aaa", "bba", "abb"

Length (n) = Length (n-1) + Length(n-2),

as we get a string of length $n$, by appending "a" to a string of length $n-1$ as well as by appending "bb" to a string of length $n-2$. (This works only because 'a' and 'bb' doesn't have a common character). 

So, 

n	No. of strings
1	1
2	2
3	3
4	5
5	8
6	13
7	21
8	34
9	55
10	89

We get no. of strings = 89 (10th Fibonacci number) 

Comments

we get a string of length n, by appending "a" to a string of length n-1  as well as by appending "bb" to a string of length n-2 .

But we can append either in Beginning or in End. so, Should we multiply with 2 ??

and if something is common like "appending a to aa"  > aaa (appending in beginning and end results in same strings) . Then how to identify ??How r u counting these??

---

Sir what is wrong in my approach , since we want the length of string to be 10 , so first case when all are a so only 1 way , another case when all are b's so again 1 way ,Now for the remaining cases

1. 8 a's and 1 bb , no of way =10C8

2.6 a's and 2 bb   ,no of ways =10C6

3. 4 a's and 3 bb , no of ways =10C4

4. 2 a's and 4 bb ,no of ways =10C2

Now summing these all I am getting the answer as 512 , what is wrong in this logic ?

---

@radha there are mistakes 

as instead of 10C8 it should be 9C8, similarly 10C6 should be 8C6

and you left one option for 0 bb

check it, https://gateoverflow.in/31927/tifr-2015-maths-b-10

---

Sir I got the the logic for first case since we have bb together so 9 choices but second logic I couldn't get since I have already considered the case where all 10 positions are a's so only 1 way .

---

those strings will have 2 bb will never be same as those having 1 bb. there will be no relation with previous.