• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Comp Sci Induction Proof for all strings: Can't understand the Question

  • Thread starter zak100
  • Start date
387
9
Homework Statement
Use induction on 'n' to show that |t^n| = n |t| for all strings 't' and for all 'n'.
Homework Equations
No equation
Hi,
Can some body please explain me the following question:
Use induction on ##n## to show that ##|t^n| = n |t| ## for all strings ##t## and all ##n## .

Any idea how to that. I know we have a base case and an induction case but what would be the base case and what would be the induction case?

Zulfi.
 

QuantumQuest

Science Advisor
Insights Author
Gold Member
858
436
As you're asked to do a proof by induction, you have to think about some property / ies of strings having to do with numbers. Also, what does ##|t^n|## mean? A potential hint might be towards concatenation. Then, you'll be ready to construct the base case and proceed further.
 
387
9
Hi,
Base case : Let n=0
##t^0= \text {empty string}##

##\text {Now suppose} ## ## n= k ##

##t^n = t^k##

##= k |t|##

##\text{Induction Step: Let } n = k+1##

##t^n = t^{(k+1)}##

##= k|t|. 1|t|##

##= t^n. 1|t|##

Some body please correct me.
Zulfi
 

QuantumQuest

Science Advisor
Insights Author
Gold Member
858
436
What property / properties of strings do you consider?Also, what does ##|t^n|## mean?
 
387
9
Hi,
Length of t^n

Zulfi.
 
387
9
I think : |t| = length of string t

Zulfi.
 
387
9
Hi,
I think ##|t^n|## means a string of size 'n'.

Zulfi.
 
32,626
4,364
I think ##|t^n|## means a string of size 'n'.
I don't think so. ##t^n## probably represents a string with n characters, and ##|t^n|## might mean the length of such a string. Since you aren't sure, you better make sure that's the case.
zak100 said:
Base case : Let n=0
##t^0= \text {empty string}##
I would start with a base case of n = 1, a string that contains one character.
zak100 said:
##\text {Now suppose} ## ## n= k ##
##t^n = t^k##
##= k |t|##
This is the Induction Hypothesis; i.e., if n = k, then ##t^k = k|t|##
Here I'm also assuming that ##|t| = |t^1|##; i.e., that |t| is shorthand for the length of a string with one character.
zak100 said:
##\text{Induction Step: Let } n = k+1##

##t^n = t^{(k+1)}##

##= k|t|. 1|t|##

##= t^n. 1|t|##
This isn't right. Wouldn't ##|t| \cdot |t|## be equal to ##|t|^2##? (Which may or may not be equal to 1.)
In any case, you need to use the Induction hypothesis to show that ##|t^{k + 1}| = (k + 1)|t|##.

This is probably a lot simpler problem than you are making it. With regard to strings, what do the expressions ##|t^k|## and ##|t^{k+1}|## represent?
 
387
9
Hi,

Thanks for the steps.

From the proposition, it seems that :
##|t^n|= n|t| ##

##\text {but I don't think we can use the proposition:} ##

##\text & ##

##|t^{(k + 1)} | = |t^k . t^1| ##

Zulfi.
 
32,626
4,364
Hi,

Thanks for the steps.

From the proposition, it seems that :
##|t^n|= n|t| ##
Well, this is exactly what you need to prove.
zak100 said:
##\text {but I don't think we can use the proposition:} ##

##\text & ##

##|t^{(k + 1)} | = |t^k . t^1| ##
Of course you can't -- you can't use something that you're supposed to prove.
Take a look again at what I wrote in post #10:
With regard to strings, what do the expressions ##|t^k|## and ##|t^{k+1}|## represent?
 
32,626
4,364
@zak100, you will never be able to do this problem if you can't answer the question @QuantumQuest asked way back in post #2.
Also, what does ##|t^n|## mean? A potential hint might be towards concatenation.
His hint that ##t^n## represents the concatenation of a string t with itself some number of times seems to be the best interpretation of this notation.
 
387
9
Hi,
If a person is not able to understand please use simple words. If you had used multiplication (instead of concatenation) even in brackets followed by concatenation, my life could have become more easier at that time.

Zulfi.
 
32,626
4,364
If a person is not able to understand please use simple words. If you had used multiplication (instead of concatenation) even in brackets followed by concatenation, my life could have become more easier at that time.
Our life, and yours, would have become easier if you had explained what ##t^n## means right at the beginning of this thread.

I realize that English is not your first language. To concatenate two strings means that the two strings are joined together to form a single string. For example, the concatenation of "bad" and "dog" results in the string "baddog".

I believe that @QuantumQuest is on the right track regarding the meaning of ##t^n##. If t = "abc", then it is likely that ##t^2## represents a string formed from two copies of t; that is, the string "abcabc". From this it is reasonable to assume that ##|t| = 3## and ##|t^2| = 6##, but we don't know this for a fact, since you haven't told us what the notation ##t^n## means, despite being asked for it several times in this thread. The reason you're struggling with this problem is that you aren't clear about what ##t^n## means.
 

Want to reply to this thread?

"Induction Proof for all strings: Can't understand the Question" You must log in or register to reply here.

Related Threads for: Induction Proof for all strings: Can't understand the Question

  • Posted
Replies
1
Views
584
  • Posted
Replies
6
Views
2K
Replies
1
Views
1K
  • Posted
Replies
3
Views
1K
Replies
7
Views
8K
  • Posted
Replies
11
Views
3K
  • Posted
Replies
1
Views
1K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top