Stuck on a recursion question

[tomtomru]

I've been stuck on this recursion question for about 2 days now and still can't find a way to solve the following. I've managed to find what t2 and t3. I've tried to solve a, b and c using simultaneous equations by first finding t4, t5 and t6, and got the answers: a = -11, b = 41 and c = -31. But I'm totally sure that my answers are wrong. And the method I've used to find t4, t5 and t6 seems a bit redundant and long. So I'm wondering if there's an alternative and perhaps correct way to solve this problem.

And as for the last multiple choice question, I'm really unsure about what the question is asking and how to find the answer.

Any help is appreciated! Thanks!

 

[Dr.Peterson]

I've been stuck on this recursion question for about 2 days now and still can't find a way to solve the following. I've managed to find what t2 and t3. I've tried to solve a, b and c using simultaneous equations by first finding t4, t5 and t6, and got the answers: a = -11, b = 41 and c = -31. But I'm totally sure that my answers are wrong. And the method I've used to find t4, t5 and t6 seems a bit redundant and long. So I'm wondering if there's an alternative and perhaps correct way to solve this problem.

And as for the last multiple choice question, I'm really unsure about what the question is asking and how to find the answer.

Any help is appreciated! Thanks!
View attachment 32739View attachment 32740

Did you try using the problem itself, rather than (presumably correct!) values of several terms in the sequence, to write the recursion?

If you know the legal strings with 1, 2, and 3 letters, how can you use those to find all legal strings with 4? More generally, how can you form all strings with n letters, when you know those with n-1, n-2, and n-3?

Also, what did you get for [imath]t_4, t_5, t_6[/imath]?

 

[Dr.Peterson]

I've been stuck on this recursion question for about 2 days now and still can't find a way to solve the following. I've managed to find what t2 and t3. I've tried to solve a, b and c using simultaneous equations by first finding t4, t5 and t6, and got the answers: a = -11, b = 41 and c = -31. But I'm totally sure that my answers are wrong. And the method I've used to find t4, t5 and t6 seems a bit redundant and long. So I'm wondering if there's an alternative and perhaps correct way to solve this problem.

And as for the last multiple choice question, I'm really unsure about what the question is asking and how to find the answer.

I'll make a couple more comments.

First, since my formula yields the same values as yours for t_4 and t_6, I suspect that you got 29 instead of 35 for t_5. It's risky to do such counting by hand, in addition to being a lot more work your way. Have you tried my hints yet?

Second, the multiple choice question is easily solved using thinking similar to that for finding the recursion in the first part.

 

[tomtomru]

I'll make a couple more comments.

First, since my formula yields the same values as yours for t_4 and t_6, I suspect that you got 29 instead of 35 for t_5. It's risky to do such counting by hand, in addition to being a lot more work your way. Have you tried my hints yet?

Second, the multiple choice question is easily solved using thinking similar to that for finding the recursion in the first part.

Thanks for your reply!
Yes. Previously I had calculated t4, t5 and t6 by hand and using combinations to solve it just because I'm not familiar with any other other way, and I realise it can be very tedious and higher chance of getting the wrong value while doing so. So instead this time I have tried calculating for t4 using the formula tn = (tn-1) + 1. It seems to work for t1, t2, t3 and t4, but when I get to the 5th term it doesn't seem to output t5 = 35. Am I doing something wrong here?

I'm still in the midst of thinking how to solve the multiple choice question...

 

[Dr.Peterson]

Thanks for your reply!
Yes. Previously I had calculated t4, t5 and t6 by hand and using combinations to solve it just because I'm not familiar with any other other way, and I realise it can be very tedious and higher chance of getting the wrong value while doing so. So instead this time I have tried calculating for t4 using the formula tn = (tn-1) + 1. It seems to work for t1, t2, t3 and t4, but when I get to the 5th term it doesn't seem to output t5 = 35. Am I doing something wrong here?

I'm still in the midst of thinking how to solve the multiple choice question...

Why do you think that is the right formula? And it obviously doesn't work for any terms. Can you show more details?

 

[tomtomru]

Why do you think that is the right formula? And it obviously doesn't work for any terms. Can you show more details?

Okay! I did some thinking and I think I've got it!! Here's my solution. Would appreciate if you could check if I'm doing this correctly. Thanks!

Every legal string of n letters can be written in exactly one of the following ways:
- Xv where X is a legal string of length n-1
- Xww where X is a legal string of length n-2
- Xxx where X is a legal string of length n-2
- Xyyy where X is a legal string of length n-3
- Xzzz where X is a legal string of length n-3

So tn would be tn-1 + 2tn-2+ 2tn-3 for all n>=4

 

[Dr.Peterson]

Okay! I did some thinking and I think I've got it!! Here's my solution. Would appreciate if you could check if I'm doing this correctly. Thanks!

Every legal string of n letters can be written in exactly one of the following ways:
- Xv where X is a legal string of length n-1
- Xww where X is a legal string of length n-2
- Xxx where X is a legal string of length n-2
- Xyyy where X is a legal string of length n-3
- Xzzz where X is a legal string of length n-3

So tn would be tn-1 + 2tn-2+ 2tn-3 for all n>=4

Yes, it looks like you're thinking now.

Have you tried using this to generate several terms of the sequence? What do you get? (I like to use a spreadsheet to do this.)

Then try using similar thinking for the other part.

 

[tomtomru]

Yes, it looks like you're thinking now.

Have you tried using this to generate several terms of the sequence? What do you get? (I like to use a spreadsheet to do this.)

Then try using similar thinking for the other part.

Okay I think I've figured out how to write the recursion for pn, which would be
pn = tn - tn-1 - tn-2.
And I've also generated the values of You t1-t101 and p1-p101 on a spreadsheet. However given the multiple choice options, I still am unable to get the correct answer.

Basically my p101 on my spreadsheet generated 1.87911E+35. And the closest option to choose from the MCQ is p100+p99 which my spreadsheet generated as 1.1928E + 35.

Is the recursion for pn wrong in this case? Should I be writing pn in terms of pn instead of tn?

 

[Dr.Peterson]

Okay I think I've figured out how to write the recursion for pn, which would be
pn = tn - tn-1 - tn-2.
And I've also generated the values of You t1-t101 and p1-p101 on a spreadsheet. However given the multiple choice options, I still am unable to get the correct answer.

Basically my p101 on my spreadsheet generated 1.87911E+35. And the closest option to choose from the MCQ is p100+p99 which my spreadsheet generated as 1.1928E + 35.

Is the recursion for pn wrong in this case? Should I be writing pn in terms of pn instead of tn?

They aren't asking for a recursion for p_n! They want an expression for one particular count.

Perhaps I shouldn't have said it would be "similar", which you are taking to mean "the same". I meant to think about how you can make a sequence of the new type. And I didn't say to use a spreadsheet as part of your solution; I just do that to check recursions.

And you should tell us your thinking, not just your formula and your check.

 

[Cubist]

OP, please think about what happens if the number of letters is even. In order for the string to read the same backwards then you could have...

"any legal string of length n₁" followed by a "ww" followed by "what?"

What must n₁ be if the total desired number of letters is n?
How many combinations are possible with the pattern above?
Are there any other patterns that could produce legal, reversible, strings?

 

[Dr.Peterson]

OP, please think about what happens if the number of letters is even. In order for the string to read the same backwards then you could have...

"any legal string of length n₁" followed by a "ww" followed by "what?"

What must n₁ be if the total desired number of letters is n?
How many combinations are possible with the pattern above?
Are there any other patterns that could produce legal, reversible, strings?

Of course, what is asked for has an odd number of letters, so this is just an illustration, not an answer.