-1

Let

$$T(n):=\begin{cases} 3 & \text{if }n=1\\ 4 \cdot T(n/4) + 3 & \text{if }n>1\end{cases}$$

Prove that $T(n) = 4n − 1$ for all $n \geq 1$.

Base case: When $n = 1$, LHS $= T(1) = 3$, RHS $= 4 \cdot 1 − 1 = 3$. Therefore, LHS = RHS

LHS = Left hand side RHS = right hand side

Can somebody explain to me how RHS has been transformed into RHS $= 4 \cdot 1 − 1 = 3$ from $T(1) = 4 \cdot T(n/4) + 3$ ? Thanks

b00n heT
  • 16,360
  • 1
  • 36
  • 46
Tudor
  • 1
  • Is this problem complete? Do we know anything else about $T$? – iamvegan Aug 21 '16 at 12:33
  • T seems to be defined only for $n$ equal to multiples of $4$ (i.e. $n=4k$ where $k\in\mathbb{N}$). Regarding your questions though, for the base case, the LHS is the definition of $T(1)$ which is $3$ and the RHS is the assignment of $n=1$ in $4n-1$. – Daugmented Aug 21 '16 at 12:40

1 Answers1

0

For $n=1$ we have that $T(1)=3=4\cdot 1-1$. Thus the two definitions agree and hence the induction start holds.

Now assume the claim to be true for all indexes up to $\;n\;$, and go for $\;n+1\;$ :

$$T(n+1):=4T\left(\frac{n+1}4\right)+3\stackrel{\text{Ind. Hypot.}}=4\left(4\frac{n+1}4-1\right)+4=$$

$$=4n+4-4+3=4n+3=4(n+1)-1$$

b00n heT
  • 16,360
  • 1
  • 36
  • 46
DonAntonio
  • 211,718
  • 17
  • 136
  • 287
  • Not true. You are assuming $\frac{n+1}{4}$ is an integer. – iamvegan Aug 21 '16 at 12:33
  • The proof seems correct, but I don't see why $T(n)$ is well defined.. – b00n heT Aug 21 '16 at 12:34
  • @iamvegan Not necessarily. Either the function is defined in a wider domain than the naturals and we're only given what the OP wrote, or else the claim is for multiples of four. – DonAntonio Aug 21 '16 at 12:34
  • 1
    @b00nheT Indeed so, b00n. Perhaps the OP left a condition out, or else (s)he didn't explain correctly the problem. – DonAntonio Aug 21 '16 at 12:35
  • The function can be defined on reals, that part is okay. However, if you are doing induction, you can do it on integer $n$. You can not assume ind. hyp. on $\frac{n+1}{4}$ if it is not an integer. – iamvegan Aug 21 '16 at 12:36
  • You can't even show $T(2)=7$ – iamvegan Aug 21 '16 at 12:38
  • @iamvegan Of course you can do induction on something that's somehow numbers by a well ordered set (and regular induction even if the set is countable). Anyway, I think the OP either misdefined that function or else he ommited some oter data. – DonAntonio Aug 21 '16 at 12:39
  • But that's not what you are doing here. Your argument is false even for $n=2$, because you don't know the value of $T(1/2)$. Moreover $1/2$ is less then your starting value $n=1$. – iamvegan Aug 21 '16 at 12:44