Proof by induction

how to prove that recursive relation is divisible by 3 for n>=1

Base case T(1)=3 is easy. Not sure about the rest

you just have to assume that your hypothesis is true for all k

want T(n)=T(n-1)+2T(floor(n/2)) to be divisible by 3

*waves induction wand, making T(n-1) and T(floor(n/2)) divisible by 3*

so T(n-1)=3a for some integer a, and T(floor(n/2))=3b for some integer b

so T(n)=3a+3b=3(a+b), so T(n) is divisible by 3

Induction made much more sense to me after seeing it defend in hugged order logic:

∀P((0∈P∧∀i(i∈P-->i+1∈P))-->∀n(n∈P))

So we have two conditions that must be true to ensure the implication: the base case and an additional implication.

Figured it out OP, here's the proof

Proof:
(let t(n)=T(n) since I'm too lazy to press shift, let [x]=floor function of x, and let "==" denote modular congruency, also "a|b" means "a is divisible by b")

Consider t(n)=t(n-1)+2t([n/2]) and that t(0)=1

Base Case: t(1) = t(1-1)+2t([1/2]) = t(0)+2t(0) = 3t(0) = 3*1=3 which is divisible by 3

Induction: Suppose t(n)|3 for all 1

Thought of a much better proof after I hit send that doesn't need the lemma

assume I proved the base case like before

Induction: let t(n)|3 for 1

hmmm now that I look at it again, since 1

or better for the induction step, just let 0

My OCD won't let me leave this proof looking this ugly. Here's the complete proof.

Proof:
Base Case: For n = 1
t(1) = t(0)+2t([1/2]) = 1+2t(0)=1+2=3

Induction: let t(n)|3 for 0