Consider the following three claims 1. (n + k)m = Θ(nm), where k and m are…

Answer: claims 1 and 2 are correct; claim 3 is incorrect.

• Claim 1: (n + k)^m = Θ(n^m). True. Write (n+k)^m = n^m(1 + k/n)^m. For fixed k and m, (1 + k/n)^m tends to 1 as n → ∞, and for sufficiently large n it is bounded above and below by positive constants. Thus there exist constants c1,c2,n0 such that for n ≥ n0, c1 n^m ≤ (n+k)^m ≤ c2 n^m, so (n+k)^m = Θ(n^m).

• Claim 2: 2n + 1 = O(2n). True (interpreting 2n as 2·n). For n ≥ 1 we have 2n + 1 ≤ 3n, and 3n = (3/2)·(2n). So choosing c = 3/2 and n0 = 1 gives 2n + 1 ≤ c·(2n) for all n ≥ n0, proving 2n + 1 = O(2n).

• Claim 3: 22n + 1 = O(2n) (interpreted as 2^{2n+1} = O(2^n)). False. If the intended meaning is exponential 2^{2n+1} compared to 2^n, then the ratio is 2^{2n+1}/2^n = 2^{n+1}, which tends to infinity as n grows. Therefore no constant c can satisfy 2^{2n+1} ≤ c·2^n for all large n, so the claim is not true. (If someone read the expression as a different linear form, that would be a different statement, but the usual intended reading in this context is exponential and it is false.)

Conclusion: only claims 1 and 2 are correct.