Induction: There are two one-letter words in English (“I” and “a”),...

[footy_rover]

Induction: There are two one-letter words in English (“I” and “a”),...

There are two one-letter words in English (“I” and “a”), and according to http://www.scrabble.org.au/words/twos.htm there are 124 two-letter words.Let A_n be the number of strings of n letters that may be formed from some sequence of one- andtwo-letter words, by concatenating them all together.

Find a₃

Give an expression for a_n in terms of a_n−1 and a_n−2, that works for all n ≥ 3.

So far a₁ makes sense to just be "I" and "a" so a total of 2.
a₂ would be the 124 two letter strings plus a combination of 2² that can be such as ai, ia, ii, aa but since ai and aa are already present as part of the 124 two letter strings a₂ is actually 126.

Would a₃ be when each of those 124 two letter words be concatenated to either the letter I or the letter a? Bit confused here

 

[tkhunny]

Does it say unique strings?

 

[stapel]

There are two one-letter words in English (“I” and “a”), and...there are 124 two-letter words. Let A_n be the number of strings of n letters that may be formed from some sequence of one- and two-letter words, by concatenating them all together.

Find a₃

What is "a₃"? How does it relate (if at all) to "A_n"?

Also, your subject line refers to "Induction". Are you supposed to be using induction to prove some sort of formula? Thank you!

 

[mmm4444bot]

Let A_n be the number of strings of n letters that may be formed from some sequence of one- and two-letter words, by concatenating them all together.

In the absence of other information, we need to assume that "some sequence" means "any sequence".

Give an expression for A_n in terms of A_n−1 and A_n−2, that works for all n ≥ 3.

So far A₁ makes sense to just be "I" and "a" so a total of 2. Yes, A₁=2

A₂ would be the 124 two letter strings plus a combination of 2² that can be such as ai, ia, ii, aa but since ai and aa are already present as part of the 124 two letter strings A₂ is actually 126.

Would A₃ be when each of those 124 two letter words be concatenated to either the letter I or the letter a?

That's partially correct. We're concatenating "I" and "a" with those 124 two-letter words, but also with the two 2-character strings "Ia" and "II" (because they may each be formed by concatenating one-letter words with themselves).

A₃ is the count of all three-character strings that may be formed by concatenating "I" or "a" both before and after each of the 126 two-letter strings and with each other -- minus all the duplicates.

It's easier for me to pull out "aI" and "aa" from the list of 124 two-letter words, so that I can consider them along with "Ia" and "II"

In other words, I'm thinking of A₂ = 122 + 4, where those 4 are "aa", "aI", "Ia", and "II".

With these interpretations, I count 488 three-character strings formed by concatenating each of "I" and "a" both in front and back of the 122 two-letter words, plus another 18 strings formed by concatenating "I" with itself ("III") and "a" with itself ("aaa") and each of "I" and "a" in front and back of "aa", "aI", "Ia", and "II". Ten of these 18 are duplicates.

4*122 + 18 - 10 = 496

Before we can find a recursive pattern (if one exists, after eliminating duplicates), I think that we'll need to determine more values in the sequence A_n. You up for finding A₄?

Also, tkhunny asked a good question. Are we sure the author of this exercise was eliminating duplicates? :cool: