Using induction on n prove the following For any collection

Using induction on \"n\" prove the following:

For any collection of strings z_1, z_2, ... z_n reverse(z_1 z_2 ... z_n) = reverse(zn) verse(z_n-1) ... reverse(z_1).

Solution

reverse(z1.....zn) = reverse(zn)reverse(zn-1)....reverse(z1)

proof by indution-

basis step -

for n=1, see if this holds. this is trivial, it will hold as reverse(z1) = reverse(z1)

induction step -

now we\'ll assume that this holds for some n=k where k is an integar.

so

reverse(z1...zk) = reverse(zk)reverse(zk-1)....reverse(z1)

NOW, to prove our induction hypothesis , we must show that this holds for (k+1) strings asssuming that it held for k strings.

let us look at what effect the (k+1)th string will have on our strings. first let us see an example then we\'ll generalize. exm -

for n=3, strings abc, def, ghi will hold with-

reverse(abcdefghi) = reverse(ghi)reverse(def)reverse(abc)

ihgfedcba=ihgfedcba

this holds, so let us introduce a 4th string xyz,

reverse(abcdefghixyz)=reverse(xyz)reverse(ghi)reverse(def)reverse(abc)

in RHS,the last 3 strings have shown to be equal to reverse(abcdefghi) above! so it becomes

reverse(abcdefghixyz)=reverse(xyz)reverse(abcdefghi)

now, look at RHS, it now only has two strings, so now it is trivial to see that LHS=RHS (as reverse(ba) can always be written as reverse(b) reverse(a))

therefore, it becomes zyxihgfedcba=zyxihgfedcba

that was our proof!

let us generalise this now, for k+1 strings

reverse(z1...z2...zk) = reverse(z1) reverse(z2)........reverse(zk)

reverse(z1...zk)reverse(zk+1)=reverse(z1)reverse(z2)........reverse(zk)reverse(zk+1)

but reveerse(z1..zk)reverse(zk+1)=reverse(z1....zk+1)= reverse(z1..zk+1)

therefoere

reverse(z1...zk)=reeverse(z1).reverse(z2)........reverse(z+1)

hence proved!

----------

thank you