I recently was introduced to solving recurrence bounds by substitution but there's something i don't understand about it.
In standard induction proofs you prove a base case, assume it holds for n then show it holds for n+1 and therefore show it applies to integers larger than the base case.
For when you solve recurrences like T(n) = T(n/2) the proof has a base, assumes T(n/2) then proves it holds for T(n). Does this proof not only hold for the numbers that are multiples of two of the base cases? Would this not require an infinitely large number of base cases to show what it holds for?
Could someone please explain this to me?