I am trying to solve this recurrence relation $$ f(a,b)=cf(\lceil\frac{a}{c}\rceil,b)+cf(a,b-1). $$ The base cases are $f(a,2)=a$, $f(1, b)=1$, $c\geq{2}$, and $a, b, c\in{\mathbb{Z}^+}$. I tried to expand this relation, but I am confused about the termination conditions for different branches. Can anyone give me some clue about how to solve this recurrence relation?
Asked
Active
Viewed 22 times
0
-
What is the domain of the variables? IE must $a/c$ b an integer? – Calvin Lin Nov 10 '19 at 16:08
-
Letting $ c = 1$, we have $ f(a,b) = f(a,b) + f(a,b-1)$. Hence, $f(a,b-1) = 0 $ for all values, which is a contradiction. Can you recheck your recurrence relation? – Calvin Lin Nov 10 '19 at 16:09
-
@CalvinLin Updated. Sorry for the confusion. – Snjór Nov 10 '19 at 17:11