# Proofing – How to prove the function of a recursive big theta without using repeated substitution, mastering the sentence, or having the closed form?

I have defined a function: $$V (j, k)$$ Where $$j, k in mathbb {N}$$ and $$t> 0 in mathbb {N}$$ and $$1 leq q leq j – 1$$, Note $$mathbb {N}$$ includes $$0$$,

$$V (j, k) = begin {cases} tj & k leq 2 tk & j leq 2 tjk + V (q, k / 2) + T (j – q, k / 2) & j , k> 2 end {cases}$$

I am not allowed to use repeated substitution and I want to prove this by induction. I can not use the main clause because the recursive part is not in that form. Any ideas how I can solve it with given limitations?

When I start induction: I fix $$j, q$$ and introduce $$k$$, Then the base case $$k = 0$$, Then $$V (j, 0) = tj$$, The question indicated that the function may be $$Theta (jk)$$ or maybe $$Theta (j ^ 2k ^ 2)$$ (but it does not necessarily have to be either).

I choose $$Theta (j, k)$$, In the base case, this would mean that I had to prove that $$tj = theta (j, k)$$ when $$j = 0$$, But if I start with the big-oh, I have to show it $$km leq mn = m cdot0 = 0$$ which I currently do not think possible.

I am not sure if I did the basic case wrong or if there is another approach.

Posted on Categories Articles