Prove by induction or any other logical argument

In summary: you have not proved that there is a 2-to-1 correspondence between songs of length m and of length 2m+2.
  • #1
jammed
26
0

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).
 
Last edited:
Physics news on Phys.org
  • #2
hi jammed! :smile:
jammed said:
(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 … ? :wink:
 
  • #3
its by rule 2
 
Last edited:
  • #4
Its by rule 2
 
  • #5
jammed said:
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?
 
  • #6
Sorry but i don't know how to answer this question.
 
  • #7
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?
 
  • #8
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?
 
  • #9
jammed said:
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 :confused:

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 … "
 
  • #10
By rule 2 and 3 i have created another 2 songs, which are of length 2m+2...thats all i know :cry:
 
  • #11
jammed said:
(ii) Show that if there are k songs of length m then there are 2k songs of length 2m+2.
jammed said:
By rule 2 and 3 i have created another 2 songs, which are of length 2m+2

sooo …
 
  • #12
I am unable to think in the form of variable to tell you the truth.
 
  • #13
jammed said:
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 :smile:

if it isn't, then this maths aptitude test does rather indicate that you should be thinking of a different degree course
 
  • #14
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
 
  • #15
jammed said:
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)
 
  • #16
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.
 
  • #17
jammed said:
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" :smile:

(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)
 
  • #18
ok i will try to write the proof in the way you tell me. How abt the third part of the question?
 
  • #19
jammed said:
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.
jammed said:
… How abt the third part of the question?

ok, have a go! :smile:
 
  • #20
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.
 
  • #21
jammed said:
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
 
  • #22
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.
 
  • #23
jammed said:
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
 
  • #24
So i should combine your argument plus mine and that will make the proof brief and rigorous
 
  • #25
Can u tell me the variations in this type of question that is what other questions can be asked in this context
 
  • #26
jammed said:
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 :wink:

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

1. What is induction and how does it relate to logical arguments?

Induction is a method of reasoning in which a conclusion is made based on a pattern of observed evidence. It is commonly used in mathematics and logic to prove a statement or theorem by starting with a base case and then using a logical argument to show that the statement holds for all cases.

2. How do you use induction to prove a statement?

To use induction to prove a statement, you must first establish a base case, which is a specific instance of the statement that can be proven to be true. Then, you must assume that the statement holds for a particular case and use logical reasoning to show that it also holds for the next case. This process is repeated until the statement is proven to hold for all cases.

3. Can induction be used to prove any statement?

No, induction can only be used to prove statements that follow a specific pattern or have a specific structure. It cannot be used to prove statements that are not based on a pattern or that are not logically connected to each other.

4. Are there any limitations to using induction as a proof method?

Yes, there are limitations to using induction as a proof method. One limitation is that it can only be used to prove statements that follow a specific pattern or structure. Another limitation is that it can be time-consuming and tedious to use for larger or more complex statements.

5. Is induction the only way to prove a statement?

No, induction is not the only way to prove a statement. There are other proof methods, such as deduction and contradiction, that can also be used depending on the nature of the statement and the available evidence.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
7
Views
277
  • Precalculus Mathematics Homework Help
Replies
1
Views
2K
  • Precalculus Mathematics Homework Help
Replies
24
Views
2K
  • General Discussion
Replies
10
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
9
Views
3K
  • Beyond the Standard Models
Replies
0
Views
412
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
Replies
13
Views
1K
Back
Top