<s>[INST] Solving a recurrence relation with floor function I'm having trouble solving this recurrence relation:
\begin{align}
T(n) &=
\begin{cases}
2\,T\big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5\big) + n^\frac{\pi}{2} &\text{if } n > 7 \\
1 &\text{otherwise}
\end{cases}
\end{align}
where $n \in \mathbb{N}$. I would prefer to find the explicit solution for $T(n)$, but just an asymptotic bound on the solution would be enough.
I guess this is going to be done via substitution method and through induction, but I have no idea how to set it up/solve it. I assume the master theorem cannot be used here, because of the floor function.
I found two similar questions, here and here, but I don't know how their solutions can be adapted to my question.
 [/INST] Actually, after some manipulations, you can use the master theorem! Let us see how. First, let us prove the following lemma:

Lemma: The function $T$ is non-decreasing, i.e. $T(n) \leq T(n+1)$ for all $n \in \mathbb{N}$.

Proof. By strong induction on $n \in \mathbb{N}$. 
Base cases: For all $0 \leq n \leq 6$, one has $T(n) = 1 = T(n+1)$. Moreover, $T(7) = 1 < 2\,T(0) + 8^{\pi/2} = T(8)$, as $\big\lfloor \frac{8}{\sqrt{2}} \big\rfloor =5$.
Inductive step: Let $n > 7$. The strong induction hypothesis is $T(k) \leq T(k+1)$ for all $0 \leq k < n$. The goal is to prove that $T(n) \leq T(n+1)$. 
By definition,
\begin{align}
T(n) &= 2\,T\big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5\big) + n^\frac{\pi}{2} 
&
T(n+1) &= 2\,T\big(\big\lfloor \frac{n+1}{\sqrt{2}} \big\rfloor - 5\big) + (n+1)^\frac{\pi}{2}\,.
\end{align}
According to the properties of the floor function, $\big\lfloor \frac{n+1}{\sqrt{2}} \big\rfloor \leq \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor + \big\lfloor \frac{1}{\sqrt{2}} \big\rfloor + 1 = \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor + 1$, and $\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor \leq \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor + \big\lfloor \frac{1}{\sqrt{2}} \big\rfloor \leq \big\lfloor \frac{n+1}{\sqrt{2}} \big\rfloor$, since $\sqrt{2} > 1$.
Therefore, there are only two cases:


*

*either $\big\lfloor \frac{n+1}{\sqrt{2}} \big\rfloor = \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor$ and then $T(n) \leq 2\,T\big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5\big) + (n+1)^\frac{\pi}{2} = T(n+1)$, where the inequality holds because from $\frac{\pi}{2} > 0$ it follows that $n^\frac{\pi}{2} < (n+1)^\frac{\pi}{2}$ ;

*or $\big\lfloor \frac{n+1}{\sqrt{2}} \big\rfloor = \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor + 1$; we can apply the strong induction hypothesis to $T \big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor- 5 \big)$ because $\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5 < n$ (indeed, $n + 5 > n = \lfloor n \rfloor \geq \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor $ since $\lfloor \cdot \rfloor$ is non-decreasing), so $T \big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor- 5 \big)\leq T \big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor- 5 + 1\big) = T \big(\big\lfloor \frac{n + 1}{\sqrt{2}} \big\rfloor- 5 \big)$ and hence $T(n) \leq 2\,T\big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5\big) + (n+1)^\frac{\pi}{2} = T(n+1)$. $\qquad\square$
As $T$ is non-decreasing by the lemma above (and $\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5 < \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor \leq \frac{n}{\sqrt{2}}$), for $n > 7$ one has $T(n) = 2\,T\big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5\big) + n^\frac{\pi}{2} \leq 2\,T\big(\frac{n}{\sqrt{2}}\big) + n^\frac{\pi}{2}$. Therefore, if we set
\begin{align}
S(n) =
\begin{cases}
1 &\text{if } n = 0 \\
2\,S\big(\frac{n}{\sqrt{2}}\big) + n^\frac{\pi}{2} & \text{otherwise}
\end{cases}
\end{align}
then $T(n) \leq S(n)$ for all $n \in \mathbb{N}$ and so, for any function $g$, $S(n) \in O(g(n))$ implies $T(n) \in O(g(n))$, i.e. the fact that $S$ grows asymptotically no faster than $g$  implies that $T$ grows asymptotically no faster than $g$.
The point is that we can use the master theorem to find a $g$ such that $S(n) \in O(g(n))$. Using the same notations as in Wikipedia article: 
\begin{align}
a &= 2 & b&= \sqrt{2} & c_\text{crit} &= \log_\sqrt{2} 2 = 2 & f(n) &= n^{\pi/2} 
\end{align}
thus, $S(n) \in O(n^2)$ by the master theorem (since $\pi/2 < 2 = c_\text{crit}$), and hence $T(n) \in O(n^2)$.
</s>