Proof by induction

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

>>8388034
you just have to assume that your hypothesis is true for all k<n and prove it for n, since you already have it for k=1 >>8388036.

File: pepi2.jpg (620KB, 768x768px) Image search: [Google]

620KB, 768x768px

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

>>8388034
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<n<=k for some k in Z

Consider t(k+1)=t(k+1-1)+2t([(k+1)/2]
(from here on I will use the lemma I will prove at the end of this proof)

k can only be even or odd so

if kmod2==1, then
t(k+1) = t(k)+2t([(k+1)/2]) = t(k)+2t((k+1)/2)

then since 1<(k+1)/2<(k+1) then 1<(k+1)/2<k
and since (k+1)/2 is in Z
then
both t((k+1)/2)|3 and t(k)|3 by our hypothesis so (t(k)+2t((k+1)/2)|3

if kmod2==0
then t([(k+1)/2)=t(k/2)
and since 1<=k/2<k and k/2 is in Z then
t(k/2)|3
so (t(k)+2t(k/2))|3

=> by both cases above, t(k+1)|3
QED

Lemma: for k in Z, if
kmod2==1 then [(k+1)/2]=(k+1)/2
and kmod2==0 then [(k+1)/2]=k/2

Proof:
if kmod2==1 then k+1=2x for some x in Z
then [(k+1)/2]=[2x/2]=[x]=x=(k+1)/2

if kmod2==0 then k=2x for some x in Z
then [(k+1)/2]=[(2x+1)/2]=[x+1/2]=x=k/2

QED

>>8388289
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<n<k for some k in Z

Consider t(k)=t(k-1)+2*t([k/2])
if kmod2==0 then we're done since both 1<k-1<k and 1<[k/2]=k/2=x<k for some x in Z and so both terms on the right are divisible by 3 by the hypothesis

if kmod2==1 then k=(2x+1) for some x in Z
then t([k/2])=t([(2x+1)/2])=t([x+1/2])=t(x)
and since 1<k-1<k and 1<x<k then both terms on the right are divisible by 3.

QED

>>8388294
hmmm now that I look at it again, since 1<n<k then we're not proving the situation when k=2
so add the case t(2) to the base case and I think you'll be fine.

Also now that I look at it, this is really cool since this is also a proof that t(n)=t(n-1)+t([n/2]) is divisible by 3 for all n in Z such that n>1 as long as you let t(1)=3 by definition

>>8388310
or better for the induction step, just let 0<n<k and then you'll just need to prove that t(1)|3 for the base case. It's late

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<n<k for some k in Z

Consider t(k)=t(k-1)+2*t([k/2])
if kmod2==0 then we're done since both 0<k-1<k and 0<[k/2]=k/2=x<k for some x in Z and so both terms on the right are divisible by 3 by the hypothesis.

if kmod2==1 then k=(2x+1) for some x in Z
then t([k/2])=t([(2x+1)/2])=t([x+1/2])=t(x)
and since 0<k-1<k and 0<x<k then both terms on the right are divisible by 3.

QED

>>8388310
actually what's really cool is that you can prove that t(n)=t(n-1)+2*t([n/2]) is divisible by whatever number you want as long as you choose t(0) the right way

>>8388034
Base case: T(1)=T(0)+2T(0)=3T(0)
Inductive case: assume for n<N
T(N)=T(N-1)+2T(N/2)%3 =T(N-1)%3+2T(N/2)%3 = 0 + 2*0 = 0 QED.

>>8388334
nigger you just went full retard

>>8388334
can't just assume [N/2] is a positive integer

>>8388348
actually you can
move aside brainlets better proof coming through


base: t(1)=t(0)+2t([1/2])=3t(0)

induction: t(n)|3 for 0<n<k for k in Z
consider t(k)=t(k-1)+t([k/2])
since 0<k-1<k, and by our choice of k we get [k/2] is in Z and 0<[k/2]<k then
t(k)|3 for all k in Z
QED

>>8388348
>can't just assume floor[N/2] is a positive integer

>CS majors

>>8388367
>what if N=1

>brainlets

File: 1474628988775.jpg (68KB, 800x526px) Image search: [Google]

68KB, 800x526px

This thread
My fucking sides.
It's too early for this, holy shit.

>>8388795
this is how iron sharpens iron anon
through passive aggressive bullshit

>>8388803
The
>>move aside brainlets
Fucking killed me.

Nice proof anon, I r8 -1/12 / e^-2ipi :^)

File: how to math.jpg (42KB, 640x637px) Image search: [Google]

42KB, 640x637px

>>8388807
thanks man, I didn't major in math just for the $300K/year salary

>>8388793
>>what if N=1
That's the base case nigger.

>>8389153
>assume for n<N
>OP clearly states n>=1
>using "it's the base case" as any sort of argument
>the "proof" you posted is gibberish

Does it hurt to be a brainlet?