Prove by induction or any other logical argument

[jammed]

Homework Statement

Songs of the Martian classical period had just two notes (let us call them x and y) and
were constructed according to rigorous rules:
I. the sequence consisting of no notes was deemed to be a song (perhaps the most
pleasant);
II. a sequence starting with x, followed by two repetitions of an existing song and
ending with y was also a song;
III. the sequence of notes obtained by interchanging xs and ys in a song was also a
song.
All songs were constructed using those rules.
(i) Write down four songs of length six (that is, songs with exactly six notes).
(ii) Show that if there are k songs of length m then there are 2k songs of length 2m+2.
Deduce that for each natural number there are 2^n songs of length (2^n+1) − 2.
Songs of the Martian later period were constructed using also the rule:
IV. if a song ended in y then the sequence of notes obtained by omitting that y was
also a song.
(iii)What lengths do songs of the later period have? That is, for which natural numbers n
is there a song with exactly n notes? Justify your answer.

Homework Equations

No equations needed.

The Attempt at a Solution

The (i) part was really easy. I used the second rule and third rule to produce the four songs of length 6. The four songs were as follow: xxyxyy, xyxyxy, yyxyxx and yxyxyx. In the second part I tried to use every method possible (even induction) but cannot come to a solution. Same is the case with (iii).

 

[tiny-tim]

hi jammed!

(ii) Show that if there are k songs of length m then there are 2k songs of length 2m+2.

if a song has length 2m+2, the only way of producing it is by … ?

 

[jammed]

its by rule 2

 

[jammed]

Its by rule 2

 

[tiny-tim]

its by rule 2

well, yes, since rule 2 is the only rule that makes a song longer

can you be more precise …

how is any particular song of length 2m+2 made up?

 

[jammed]

Sorry but i don't know how to answer this question.

 

[tiny-tim]

hmm … you really should have got this by now

try it this way …

if X is a song of length m, how many songs of length 2m+2 with X in the middle can be created from the rules?

 

[jammed]

if there is a song k of length m then xkky and by rule 3 ykkx is also a song so we have produce another k song of 2m+2. Am i right?

 

[tiny-tim]

if there is a song k of length m then xkky and by rule 3 ykkx is also a song so we have produce another k song of 2m+2. Am i right?

that doesn't make sense

try "if there is a song k of length m then xkky and by rule 3 ykkx is also a song so the number of songs of length 2m+2 is … "

 

[jammed]

By rule 2 and 3 i have created another 2 songs, which are of length 2m+2...thats all i know

 

[tiny-tim]

(ii) Show that if there are k songs of length m then there are 2k songs of length 2m+2.

By rule 2 and 3 i have created another 2 songs, which are of length 2m+2

sooo …

 

[jammed]

I am unable to think in the form of variable to tell you the truth.

 

[tiny-tim]

I am unable to think in the form of variable to tell you the truth.

you should by now immediately see how to prove (ii)

if it's night-time where you are, then have some sleep :zzz:, and you'll see it in the morning

if it isn't, then this maths aptitude test does rather indicate that you should be thinking of a different degree course

 

[jammed]

First of all thank u for being rude. That has really helped.
If there is a song k of length m than by rule 2 we have produced another song of length 2m + 2 so if there are k songs of length m then there will be k songs of length 2m+2. Now to produce other songs of length 2m+2 we have to swap the xs and ys. So in total there are 2k songs of length 2m+2.
Now what do you have to say on this solution

 

[tiny-tim]

If there is a song k of length m than by rule 2 we have produced another song of length 2m + 2 so if there are k songs of length m then there will be k songs of length 2m+2. Now to produce other songs of length 2m+2 we have to swap the xs and ys. So in total there are 2k songs of length 2m+2.

yes, that's the right idea, but it's nowhere near rigorous enough to be a proof

you need to prove a 2-to-1 correspondence between songs of length m and of length 2m+2, all you have proved is that it can't be more than 2-to-1 (you haven't eliminated the possibility of getting the same song in two different ways)

you have shown that for every song X of length m there are songs xXXy and yYYx

you need to show that for every song X of length m there are songs xXXy and yXXx

(and you need to mention that the second song requires Rule III twice)

 

[jammed]

Now because the first songs of 2m+2 end in y and the second song of 2m+2 end in x so they are different from each other.

 

[tiny-tim]

Now because the first songs of 2m+2 end in y and the second song of 2m+2 end in x so they are different from each other.

you don't have to persuade me … i agree that the answer is correct

but to pass the test, you have to be able to write the proof out clearly briefly and rigorously …

that's what maths is, particularly so when they specifically claim to be testing "logical argument"

(and if I'm understanding your post correctly, you're still only proving that those two songs are different … which is obvious … not that no song can be produced twice from different Xs)

 

[jammed]

ok i will try to write the proof in the way you tell me. How abt the third part of the question?

 

[tiny-tim]

IV. if a song ended in y then the sequence of notes obtained by omitting that y was
also a song.
(iii)What lengths do songs of the later period have? That is, for which natural numbers n
is there a song with exactly n notes? Justify your answer.

… How abt the third part of the question?

ok, have a go!

 

[jammed]

Ok...
now if we remove the y(i.e song ending in a y) ,according to rule 4, of a song of length m then it will have length m-1
And if there is a song which ends in x we can use rule 3 to swap it and make it end in y so it will also have a length of m-1. So i think there will exist songs of all possible lengths.

 

[tiny-tim]

Ok...
now if we remove the y(i.e song ending in a y) ,according to rule 4, of a song of length m then it will have length m-1
And if there is a song which ends in x we can use rule 3 to swap it and make it end in y so it will also have a length of m-1. So i think there will exist songs of all possible lengths.

you haven't proved all possible lengths, you've only proved that m-1 is possible

 

[jammed]

No what I meant was that when m-1 was left it will also be ending in either x or y. If it is ending in x then v can again swap it to end it in y and then again remove the y to get song of m-2 length. so like this v can keep on getting songs of length m-3, m-4, m-5 etc. In the end we will be song on no notes so in this way we get all the possibilities
I don't think this is rigorous or close to the way you may be demanding. After i have tried every way, pls its my request that you write the proof of the questions so that i can know how to write them in a proper way.

 

[tiny-tim]

No what I meant was that when m-1 was left it will also be ending in either x or y. If it is ending in x then v can again swap it to end it in y and then again remove the y to get song of m-2 length. so like this v can keep on getting songs of length m-3, m-4, m-5 etc. In the end we will be song on no notes so in this way we get all the possibilities
I don't think this is rigorous or close to the way you may be demanding. After i have tried every way, pls its my request that you write the proof of the questions so that i can know how to write them in a proper way.

you can say that if there exists a song of length m, there exists a song of length m-1 (constructed in the way you defined), and therefore by induction of any length less than m

and since there exist songs (under the original rules) of indefinitely large length, that means that any length is possible

 

[jammed]

So i should combine your argument plus mine and that will make the proof brief and rigorous

 

[jammed]

Can u tell me the variations in this type of question that is what other questions can be asked in this context

 

[tiny-tim]

Can u tell me the variations in this type of question that is what other questions can be asked in this context

it could be anything …

the question won't be difficult, it'll be designed to test your ability to translate from ordinary English to short clear logic

(but if i was setting the question, it'd be about how long is a piece of string )

 

[jammed]

https://www.physicsforums.com/showthread.php?t=443248

See this thread