2^(kn) - 1 f: (n,k) -> ------------- 2^n - 1 We want to show that f(n,k) in N, for n,k in N, n>=1, k>=1. Proof by induction f(n,1) = 1 and thus in N for every n>=1 For k > 1: 2^(kn) - 1 f(n,k) = ------------ 2^n - 1 2^0 + ... + 2^(n-1) + 2^n + ... + 2^(kn-1) = --------------------------------------------- 2^0 + ... + 2^(n-1) 2^n + .... + 2^(kn-1) = 1 + ----------------------- 2^0 + ... + 2^(n-1) 2^0 + ... + 2^((k-1)n-1) = 1 + 2^n * --------------------------- 2^0 + ... + 2^(n-1) 2^((k-1)n) - 1 = 1 + 2^n * ------------------ 2^n - 1 = 1 + 2^n * f(n, k-1) Therefore if f(n, k-1) in N, f(n, k) is too. qed