Question

-

Answer 1

well its for my discrete math class, so we have to solve via induction. I was told to use 'hard' induction, which is how i was provided the first step 4C⌊n2⌋+n≤16(n2−1)2+n=4(n−2)2+n≤4(n−1).. we have to prove the statement for n=1, then prove it for n+1. its true for n=1, im confused on the proving n+1 part and subsequent proof

Answer 2

I remember trying to help you with something similar to this yesterday, and i still feel like you are missing something

could you possible take a picture of the problem?

Answer 3

word for word from the text is: refer to sequence c1, c2...defined by c1=0; cn= 4c[n/2] + n for all n > 1. Prove that cn <= 4(n-1)^2 for all n >=1. **thats basement n/2 not brackets**

Answer 4

lets try out the base case then for n = 1

c1 <= 4(1-1)^2
0 <= 0 so its true

Answer 5

he wrote this:
prove cn <= 4(n-1)^2 for all n >=1
so you let n = 1 there

Answer 6

assume arbitrary k where ck <= 4(k-1)^2 is true and prove for k+1
c(k+1) <= 4((k+1) - 1)^2

Answer 7

just a quick note you mention that we should use hard(strong) induction?
im not quite sure how to use a strong induction when only c1 is defined since strong induction requires 2 base cases

Answer 8

o wait nvm i get it
c2 = 4C[2/2] + 2
so c2 = 2

Answer 9

lets do the base case for n = 2 now

c2 <= 4(2-1)^2
so 2 <= 4 true again then do the inductive step now where we need to prove

c(k+1) <= 4((k+1) - 1)^2

Answer 10

dam this is stuff i show what i have so far:

so c(k+1) <= 4(k)^2 <= 4(k^2 +2k -2k + 1 - 1) <= 4(k-1)^2 + 8k - 4

Answer 11

tough* lol

Answer 12

im totally lost lol on the simplification there and proving the n+1

Answer 13

sorry i was never good at induction for inequalities so im kinda having a hard time thinking about how to do this and how to use the inductive hypothesis for this problem

c(k+1) = 4C⌊(k+1)/2⌋+(k+1)

Answer 14

c(k+1) = 4C[ k/2 + 1/2] + (k+1) = 4c[k/2] + 1/2 + k + 1 = 4C[k/2] + 3/2 + k
so now you want to show

4C[k/2] + 3/2 + k <= 4(k-1)^2 + 8k - 4
by inductive hypothesis 4C[k/2] + k = ck
so

c(k+1) = ck + 3/2 <= 4(k-1)^2 + 8k - 4
note ck <= 4(k-1)^2 from base case
so we need to show 3/2 <= 8k - 4
3 <= 16k - 8
11 <= 16k
note we are proving it for k >= 1
so 11 <= 16k holds for k>=1
thus it holds for k+1 so it holds for n as well

its a bit messy, i hope i did it right.. =/

Answer 15

it looks right to me, but i don't think the teacher would've assigned homework this hard no offense lol! but i will try to base the next problem off what you did and run with it so thank you.

Answer 16

lol your welcome i hope it helps you

Answer 17

i didnt use a strong induction which is prob why its harder

Answer 18

can I make a question?

Answer 19

yea sure

Answer 20

at the very first line of the proof, C [k/2 +1/2] is not a value of C ? how can 1/2 become an independent number and is took out like that? I mean, if k =7 , then C [ (k+1)/2] is C (4), which is a whole value of C 4, do I misunderstand something?

Answer 21

http://en.wikipedia.org/wiki/Floor_and_ceiling_functions
it shows the properties of the floor functions so i used that

Answer 22

where floor [x+n] = [x] + n

Answer 23

oh, this is not a math problem. It's computer science. No wonder, its language is not as I know. I am sorry, waste your time. I know nothing about it.

Answer 24

yea thats fine everything is a learning experience im not that good with cs either so i make mistakes too

i will be going off now (dinner) if theres other questions i come back and check it