Problem with Understanding Induction Proof question

Thread Starter

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?

Some body please guide me.

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?
 

Thread Starter

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

Please guide me.

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

Please guide me.

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.
 

Thread Starter

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|

Some body please correct me.
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|

Some body please correct me.
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.
 
Top