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

zak100

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.

Related Engineering and Comp Sci Homework Help News on Phys.org

QuantumQuest

Gold Member
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.

zak100

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|$

Zulfi

QuantumQuest

Gold Member
What property / properties of strings do you consider?Also, what does $|t^n|$ mean?

Hi,
Length of t^n

Zulfi.

QuantumQuest

Gold Member
Hi,
Length of t^n
Let's just start from a string $t$. What property of this would you consider?

zak100

I think : |t| = length of string t

Zulfi.

QuantumQuest

Gold Member
I think : |t| = length of string t
So, in general, the number of characters (i.e. the cardinality) of the string. Then, what is $|t^n|$?

zak100

Hi,
I think $|t^n|$ means a string of size 'n'.

Zulfi.

Mark44

Mentor
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?

zak100

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.

Mark44

Mentor
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?

Mark44

Mentor
@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.

zak100

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.

Mark44

Mentor
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.

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

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