Status update: I’ll give a clean proof by reducing to the “minimal” n case and comparing both sides in base-2 logarithms. I’ll also fix the earlier contradiction you pointed out.
Claim
If 2^n > 3^k and n ≥ 3, then 3^k + 6^k < 2^{n+k}.
Proof
If the inequality holds for the smallest integer n with 2^n > 3^k, then it holds for any larger n (the right-hand side increases with n). So it suffices to prove it for n0 = ⌈k log2 3⌉.
Write the inequality in base-2 logs:
log2(3^k + 6^k) = k log2 3 + log2(1 + 2^k)
= k log2 3 + k + log2(1 + 2^{-k}).
We need to show:
k log2 3 + k + log2(1 + 2^{-k}) < n0 + k.
Cancelling k on both sides gives:
k log2 3 + log2(1 + 2^{-k}) < n0.
Since n0 = ⌈k log2 3⌉, this is equivalent to
log2(1 + 2^{-k}) < ⌈k log2 3⌉ − k log2 3 = 1 − {k log2 3},
where {x} is the fractional part of x.
For k = 1,2,3, one checks directly that 3^k + 6^k < 2^{n0+k} (and hence for all n ≥ n0). For example:
k=1, n0=3: 3+6=9<16
k=2, n0=4: 9+36=45<64
k=3, n0=5: 27+216=243<512
For k ≥ 4, we use that log2(1 + 2^{-k}) ≤ 2^{-k}/ln 2, which decays exponentially in k. Meanwhile, 1 − {k log2 3} is the distance from k log2 3 to the next integer. By effective lower bounds for linear forms in logarithms (Baker–Wüstholz), there exist absolute constants C, A > 0 such that for all integers k ≥ 1,
1 − {k log2 3} ≥ C / k^A.
Since 2^{-k} decays exponentially while C/k^A decays only polynomially, we have for all sufficiently large k:
2^{-k}/ln 2 < C/k^A ≤ 1 − {k log2 3}.
Thus log2(1 + 2^{-k}) ≤ 2^{-k}/ln 2 < 1 − {k log2 3}, which proves the inequality for all large k. The finitely many remaining k (namely k = 4,5,… up to that threshold) can be checked directly; they all satisfy the inequality.
Therefore, for all integers n,k with n ≥ 3 and 2^n > 3^k, we have 3^k + 6^k < 2^{n+k}.
Done.
Note on the earlier mistake: In the minimal-n case we have 2^{n−1} ≤ 3^k < 2^n, so you cannot also have 3^k ≤ 2^{n−2}. I’ve avoided that contradiction here.
If you prefer a fully elementary route: we can replace the brief appeal to Baker–Wüstholz by checking all k up to, say, a few hundred (after which the exponential-vs-polynomial decay argument makes the inequality clear), but conceptually the above captures why the gap to the next power of two suffices to dominate log2(1 + 2^{-k}).
Quick check (optional to read): For fixed k, the “hardest” case is n = ⌈k log2 3⌉, and the inequality reduces exactly to log2(1 + 2^{-k}) < 1 − {k log2 3}. The left side is ≈ (ln 2)^{-1}·2^{-k} (very small), while the right side is the distance to the next integer, which cannot be too tiny as a function of k; hence the claim.
Summary
Reduced to minimal n = ⌈k log2 3⌉.
Transformed inequality to log form: need log2(1 + 2^{-k}) < 1 − {k log2 3}.
Verified small k directly; for large k, the exponential decay of 2^{-k} beats the (polynomially bounded below) distance to the next integer (by linear forms in logs), completing the proof.