Winternitz Signature Scheme Verfication

I am reading page 39 in this "Post Quantum Cryptography" book. Why does equation 15 hold? There is no further knowledge about f and you definitely cannot use any power laws. So, why is $f^{2^w-1-b_i}(f^{b_i}(x_i)) = f^{2^w-1}$ valid?

I have my doubts, because $f(x) = x+1$ is already a counterexample.

• Could you elaborate on why you think x+1 is a counterexample? – Maeher May 29 '15 at 15:10
• Because I took $f^k(x)$ as $f(x)f(x)f(x)$ and not as $f(f(f(x)))$. – null May 29 '15 at 15:19
• Yes, with poncho's answer, my comment is moot. I did not think of that possible confusion. – Maeher May 29 '15 at 15:20

In this notation, $f^k(x)$ means "apply $f$ $k$ times in succession". For example, $f^3(x)$ is defined to be $f(f(f(x)))$.
Because of this definition $f^a(f^b(x)) = f^{a+b}(x)$ holds trivially (even though we known nothing else about $f$), as the the left side means "do $f$ $b$ times, and then do it $a$ times", while the right means "do $f$ $a+b$ times".
$f(x) = x+1$ is not a counterexample. In this case, we have the simplification $f^k(x) = x+k$ (for example, $f^3(x) = f(f(f(x))) = (((x + 1) + 1) + 1) = x+3$, and so $f^{2^w-1-b_i}(f^{b_i}(x)) = 2^w - 1 - b_i + (b_i + x) = 2^w-1 + x = f^{2^w-1}(x)$