Coq - How to show that the first argument of a function is decreasing? -

Coq - How to show that the first argument of a function is decreasing? -

i'm working through this coq tutorial , i'm stuck 1 of lastly exercises. defined datatype binary representation of natural numbers , want convert natural numbers representation:

inductive bin : type := | bo : bin | : bin -> bin | t1 : bin -> bin.

my first naive approach this:

fixpoint divmod_2 (n : nat) := match n | o => (o, 0) | s o => (o, 1) | s (s n') => match (divmod_2 n') | (q, u') => ((s q), u') end end. fixpoint to_bin (n : nat) : bin := match n | o => bo | s n' => match divmod_2 n' | (q, 0) => (to_bin q) | (q, 1) => t1 (to_bin q) | (_, _) => bo end end.

coq stops @ definition of to_bin saying:

error: recursive definition of to_bin ill-formed. in environment to_bin : nat -> bin n : nat n' : nat q : nat n0 : nat recursive phone call to_bin has principal argument equal "q" instead of "n'".

so here's question: how prepare to_bin function ? have provide proof founded recursion described here ? assume there simpler solution since it's newbie tutorial ?

i think easiest solution define successor function binary naturals first, , utilize convert successor of unary naturals.

coq