# Induction with two unknown variables

I have been at this problem for a while now, and I cannot wrap my head around it. Any kind of help would be greatly appreciated!

The runtime for a sorting algorithm can be described by $$a_{1} = 3$$ and

I need to prove, that

For all $$n, k \in Z^{+}$$

I've tried to do the basestep, but even here I'm not sure if it's correct. I hope someone can help with the induction step as well.

Basecase:

$$n, k = 2$$

$$a_{2} =a_{2/2} + a_{2/2} + 3*2+1 = 13$$

$$3* 2 * 2^2 + 4 * 2^2 -1 = 39$$

$$a_n \leq 3 * k * 2^k + 4 * 2^k - 1$$ applies for the basebase, since $$13 \leq 39$$ is true.

Inductionstep:

?

• We just saw this one, but I can't find the duplicate. – Ross Millikan Jan 7 '19 at 15:05
• You just need to induct on $k$. The base case should be $k=1$ Then note that $n\le2^k\implies\left\lceil{ n\over2}\right\rceil\le2^{k-1}$ – saulspatz Jan 7 '19 at 15:16

Try to prove by induction over $$k$$ that for all $$1 \leq n \leq 2^k$$, $$a_n \leq 3k2^k+2^{k+2}-1$$.