Induction Help!

[johnny101]

Can someone show how to finalize this? I can't get a logical answer.. I showed what I have for work below:

Reference sequence: Sequence C1,C2,.. defined as

C1=0
Cn=4C⌊n/2⌋+n,∀n>1

Prove Cn≤4(n−1)^2,∀n≥1.

I have the induction as
Cn=4C⌊n2⌋+n≤16(n2−1)2+n=4(n−2)2+n≤4(n−1...

Lost after that...Can someone show the final steps..

Will appreciate help!

 

[stapel]

Can someone show how to finalize this? I can't get a logical answer.. I showed what I have for work below:

Reference sequence: Sequence C1,C2,.. defined as

C1=0
Cn=4C⌊n/2⌋+n,∀n>1

Um... Maybe I'm just slow today, but I can't make heads or tails of the formula for "Cn" (which I'm assuming means "\(\displaystyle C_n\)"). Where are the "L" and "J" coming from? How do they relate to C or n?

 

[johnny101]

I'm assuming the L and J youre talking about are the floor symbols....its discrete mathematics, there are floor and ceiling symbols that look like []

 

[JeffM]

Can someone show how to finalize this? I can't get a logical answer.. I showed what I have for work below:

Reference sequence: Sequence C1,C2,.. defined as

C1=0
Cn=4C⌊n/2⌋+n,∀n>1

Prove Cn≤4(n−1)2,∀n≥1.

I have the induction as
Cn=4C⌊n2⌋+n≤16(n2−1)2+n=4(n−2)2+n≤4(n−1...

Lost after that...Can someone show the final steps..

Will appreciate help!

Is this the problem

\(\displaystyle Given:\ C_1 = 0\ and\ C_n = 4 * C_{\lfloor n / 2\rfloor} + n\ for\ n > 1,\)

\(\displaystyle Prove:\ C_n \le 4 * (n - 1) * 2 = 8n - 8\ for\ n \ge 1.\)

It does not appear to me that you have done anything. Have you proved the proposition if n = 1?

 

[johnny101]

for some reason the problem didnt transfer right so its 4(n-1)^2 not *2 for all n >= 1. And its clearly true for n=1, i get confused on the n+1 step of the induction

 

[daon2]

its clearly true for n=1, which is where i get confused proving n+1 on the induction steps

It's a bit odd that your teacher writes 4(n-1)2 instead of 8n-8. Are you sure the problem is correct?

In any case, I would break it into cases for n even and n odd. If n is even, floor(n/2)=n/2. If n is odd, floor(n/2)=(n-1)/2

 

[johnny101]

its word for word 4(n-1)^2 for all n>=1 so yeah. I'm confused on how to verify that though via the induction, could you elaborate?

 

[daon2]

its word for word 4(n-1)^2 for all n>=1 so yeah. I'm confused on how to verify that though via the induction, could you elaborate?

What's confusing?

If n is even, then n=2k for some integer k, so floor(n/2)=k. Then n+1=2k+1 is odd. floor((n+1)/2) = k

Show

\(\displaystyle C_{n+1}=4C_k+(2k+1) < 4(2k)^2 = 4([n+1]-1)^2\) assuming \(\displaystyle C_{n}=4C_k+(2k) < 4(2k-1)^2 = 4(n-1)^2\)

 

[johnny101]

What's confusing?

If n is even, then n=2k for some integer k, so floor(n/2)=k. Then n+1=2k+1 is odd. floor((n+1)/2) = k

Show

\(\displaystyle C_{n+1}=4C_k+(2k+1) < 4(2k)^2 = 4([n+1]-1)^2\) assuming \(\displaystyle C_{n}=4C_k+(2k) < 4(2k-1)^2 = 4(n-1)^2\)

How did you go from n+1= 2k+1 to [FONT=MathJax_Math]n[FONT=MathJax_Main]+[FONT=MathJax_Main]1/[FONT=MathJax_Main]2[FONT=MathJax_Main]=[FONT=MathJax_Math]k[/FONT][/FONT][/FONT][/FONT][/FONT][/FONT]

 

[daon2]

How did you go from n+1= 2k+1 to [FONT=MathJax_Math]n[FONT=MathJax_Main]+[FONT=MathJax_Main]1/[FONT=MathJax_Main]2[FONT=MathJax_Main]=[FONT=MathJax_Math]k[/FONT][/FONT][/FONT][/FONT][/FONT][/FONT]

I didn't say that. I said the FLOOR of (n+1)/2 is equl to k. if m is odd then floor(m/2)=(m-1)/2.

 

[JeffM]

After you have shown a proof if n = 1, which you have not yet done, you can then logically deduce that

\(\displaystyle \exists\ k\ such\ that\ k \in \mathbb N,\ k \ge 1,\ and\ C_k \le 4(k - 1)^2.\)

Now as daon says, you are rather obviously going to have to break this into cases because the floor function of k / 2 is sensitive to whether k is even or odd.

So let's pick the case where k is even.

I like to do induction proofs by figuring out what is to be proved for k + 1 in terms of equivalent expressions in k.

So \(\displaystyle C_{k+1} = 4C_{\lfloor(k + 1)/2\rfloor} + (k + 1) \le 4\{(k + 1) - 1\}^2.\) That is what I want to prove.

Given that k is even in this case, \(\displaystyle k = 2j\ and\ j \in \mathbb N \implies \lfloor k/2 \rfloor = \lfloor 2j / 2\rfloor = \lfloor j \rfloor = j.\)

And \(\displaystyle k + 1 = 2j + 1 \implies \lfloor (k + 1)/2 \rfloor = \lfloor (2j + 1) / 2\rfloor = \lfloor j + (1/2) \rfloor = j.\)

So \(\displaystyle C_k = 4C_j + k\ and\ C_{k+1} = 4C_j + k + 1 \implies C_{k+1} = C_k + 1.\)

Can you figure out how to go from here?