/sci/ - Science & Math

So I was on a plane most of the day and was doodling on my tablet when I came up with this question:
Given two points in the taxicab metric space (the Euclidean space with taxicab metric) where the horizontal distance between the two points equals the vertical distance between the two points, how many unique paths between the points are there so that the path is as short as possible?
If <span class="math">r = [/spoiler] horizontal distance
<span class="math">r = 1 \to[/spoiler] 2 paths
<span class="math">r = 2 \to[/spoiler] 4 paths
<span class="math">r = 3 \to[/spoiler] 12 paths
<span class="math">r = 4 \to[/spoiler] 32 paths
What about <span class="math"> r = k[/spoiler]?
It seems pretty obvious that induction should be used, but I'm having trouble knowing how to set it up.
Any help? I've been thinking about this for a while and it's really irritating me...
Pic highly related.