# Problem with Understanding Induction Proof question

#### zulfi100

Joined Jun 7, 2012
650
Hi,
I have got 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.

#### WBahn

Joined Mar 31, 2012
26,271
So what is your base case going to be?

What is the smallest value of 'n' that you can have?

Can you show that |t^n| = n|t| for that case?

#### zulfi100

Joined Jun 7, 2012
650
So what is your base case going to be?

What is the smallest value of 'n' that you can have?

Can you show that |t^n| = n|t| for that case?

#### zulfi100

Joined Jun 7, 2012
650
Hi,
Smallest value of n can be zero.

Base case :
t^0= empty string

Now Induction case:
|t^n| = n|t|
= 0 |t|
= 0

Zulfi.

#### WBahn

Joined Mar 31, 2012
26,271
Hi,
Smallest value of n can be zero.

Base case :
t^0= empty string

Now Induction case:
|t^n| = n|t|
= 0 |t|
= 0

Zulfi.
Okay, now assume that it works for n = k.

Try to show that it works for n = k+1.

In other words, write the equation for n = k+1 in terms of the results for n = k.

#### zulfi100

Joined Jun 7, 2012
650
Hi,
Base case : Let n=0
t^0= empty string

Now suppose n= k
t^n = t^k
= k |t|
Induction Step: Let n = k+1

t^n = t^(k+1)
= k|t|. 1|t|
= t^n. 1|t|

Zulfi

#### WBahn

Joined Mar 31, 2012
26,271
Hi,
Base case : Let n=0
t^0= empty string

Now suppose n= k
t^n = t^k
= k |t|
Induction Step: Let n = k+1

t^n = t^(k+1)
= k|t|. 1|t|
= t^n. 1|t|

Zulfi
Ask yourself if that makes sense.

Let's say that t = "abc", so |t| = 3

Now let's pick k = 2

So t^k = "abc"^2 = "abcabc" and |t^k| = 6

t^(k+1) = "abc"^3 = "abcabcabc"

You are claiming that

t^(k+1) = k|t|.1|t| = 2·3.1·3 = 18

First off, t^(k+1) is a string of characters, not a value. But even if we assume you meant |t^(k+1)|, that should clearly be 9 and not 18.