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

Relevant 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]

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

Some body please correct me.
Zulfi

 

[QuantumQuest]

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

 

[zak100]

Hi,
Length of t^n

Zulfi.

 

[QuantumQuest]

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]

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]

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.

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.

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

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

Hi,

Thanks for the steps.

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

Well, this is exactly what you need to prove.

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

@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]

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.

 

[Mark44]

@zak100, did you ever complete this problem?

 

[zak100]

Hi, Thanks for your concern. I complete this problem.
|t^n| = |t.t.t.t...|
= n.|t|
= n . 1

Actually concatenation is a technical term. We use for appending strings. But here concatenation was used for multiplication. Multiplication is common in English but concatenation is not common when it is used for multiplication.
This was my concern.
Also after 17 post we did not get a solution. All is well that ends well but this post did not complete despite the fact that I followed what I was told based upon my understanding.
Zulfi.

 

[Mark44]

Actually concatenation is a technical term. We use for appending strings.

It is a technical term, but it is very commonly used in computer science as well as in most programming languages.

But here concatenation was used for multiplication. Multiplication is common in English but concatenation is not common when it is used for multiplication.

No, concatenation was not used for multiplication. You are confusing concatenation (denoted in your problem as $t^n$), with the magnitude, or length, of a string, which is denoted |t|.

In concatenation, you are "adding" or joining a string onto the end of another. If you "add" (append) a string onto itself, you get a string that is twice as long. That is, using the notation of your problem, if t = "abc", then $t^2 = "abcabc"$, so ##|t^2| = 6, twice the number of characters in string t.

 

[Mark44]

Also after 17 post we did not get a solution.

You mean that you did not get a solution, even though you were given many hints along the way.

All is well that ends well but this post did not complete despite the fact that I followed what I was told based upon my understanding.

You were asked several times throughout the thread what the notation $t^n$ meant, and it was not until post #17 that you finally answered that question. We can't give you good advice on how to solve a problem until 1) you understand what the problem is asking, and 2) you provide us with that information.