termination - Proving equivalence of well-founded recursion -

termination - Proving equivalence of well-founded recursion -

in reply question assisting agda's termination checker recursion proven well-founded.

given function defined (and else in vitus's reply there):

f : ℕ → ℕ f n = go _ (<-wf n) go : ∀ n → acc n → ℕ go 0 _ = 0 go (suc n) (acc a) = go ⌊ n /2⌋ (a _ (s≤s (/2-less _)))

i cannot see how prove f n == f ⌊ n /2⌋. (my actual problem has different function, problem seems boil downwards same thing)

my understanding go gets acc n computed in different ways. suppose, f n can shown pass acc ⌊ n /2⌋ computed a _ (s≤s (/2-less _)), , f ⌊ n /2⌋ passes acc ⌊ n /2⌋ computed <-wf ⌊ n /2⌋, cannot seen identical.

it seems me proof-irrelevance must used somehow, it's plenty have instance of acc n, no matter how computed - way seek utilize it, seems contaminate restrictions (eg pattern matching doesn't work, or irrelevant function cannot applied, etc).

termination agda