Help:=proc():print(`F(n), G(n) , CheckST(n) `):end:
#F(n): the set of sequences of 1's and 2's that
#add-up to n
F:=proc(n) local S1,S2,i:
option remember:

if n<0 then
  RETURN({}):
elif n=0 then 
 RETURN({[]}):
elif n=1 then
 RETURN({[1]}):
else
  S1:=F(n-1): S2:=F(n-2):
   {seq([1,op(S1[i])],i=1..nops(S1)),
   seq([2,op(S2[i])],i=1..nops(S2))}:
fi:

end:

#G(n)=F(n-1) union F(n-2)
G:=proc(n): F(n-1) union F(n-2): end:


#T(n,w): inputs an integer n and a Fib. seq. w
#outputs a member of G(n)
T:=proc(n,w):
[op(2..nops(w),w)]:
end:

#S(n,w): inputs a member of G(n) and outputs S(w)
S:=proc(n,w) :

if convert(w,`+`)=n-2 then
  [2,op(w)]:
elif convert(w,`+`)=n-1 then
  [1,op(w)]:
else
  ERROR(`Bad input`):
fi:
end:


CheckST:=proc(n) local S1,i:
S1:=F(n):
  {seq(evalb(S(n,T(n,S1[i]))=S1[i]),i=1..nops(S1))}:
end:


CheckTS:=proc(n) local S1,i:
S1:=G(n):
  {seq(evalb(T(n,S(n,S1[i]))=S1[i]),i=1..nops(S1))}:
end:


# CASf(n):= F(n)^2=F(n+1)*F(n-1)
# CASb(n): F(n+1)*F(n-1)=F(n)^2





# pf of CASf(n):
#F(n)^2=F(n)*(F(n-1)+F(n-2)) (by T(n))
#=F(n)*F(n-1)+F(n)*F(n-2) (by dist. law)
#=F(n)*F(n-1)+ F(n-1)^2   (by CASb(n-1) applied to the second prod.)
#=(F(n)+F(n-1))*F(n-1) (by reverse dist. law)
#=F(n+1)*F(n-1)  ( by S(n+1))


#CASf(w1,w2): inpputs a pair in F(n)xF(n) outputs
#a pair in F(n+1)*F(n-1) or returns FAIL
CASf:=proc(w1,w2) local n,v2,temp:

n:=convert(w1,`+`):


if convert(w2,`+`)<>n then
  ERROR(`Bad input`):
fi:

if n=0 then
   RETURN(FAIL):
fi:
v2:=T(n,w2):

if convert(v2,`+`)=n-2 then
  temp:=CASb(w1,v2):
  RETURN(S(n+1,temp[1],temp[2]):
else
 RETURN(S(n+1,w1),w2):

fi:
end:

# pf of CASb(n):
#=F(n+1)*F(n-1) 
#=(F(n)+F(n-1))*F(n-1)  (By T(n+1))
#=F(n)*F(n-1)+F(n-1)*F(n-1) (by dist.  law)
#=F(n)*F(n-1)+ F(n)*F(n-2) (by CASf(n-1))
#=F(n)*(F(n-1)+F(n-2) (by reverse dist.)
#=F(n)*F(n) (by S(n))


#CASb(w1,w2): inpputs a pair in F(n+1)xF(n-1) outputs
#a pair in F(n)*F(n) or returns FAIL
CASf:=proc(w1,w2) local n,v2,temp:

n:=convert(w1,`+`)-1:


if convert(w2,`+`)<>n-1 then
  ERROR(`Bad input`):
fi:

if n=1 then
 #Coming-Up  
fi:



end: