Week #8. Assignmnet 2

using Fibonacci number to proof "Odd Maximal Contiguous Ones Free Strings are binary strings that contain no maximal contiguous substring1of 1s that is of odd length."

first thing is to observe.

all previous OMCOFS elements append "0" or "11", is still OMCOFS.
all non-OMCOFS elements append "0" or "11", is still non-OMCOFS.

using the formula from "INTRODUCTION TO THE THEORY OF COMPUTATION" P78 to proof the assumption.

WEEK #6 @ T(n)

upper bound on T(n):

 T(n) >= c ·lgn  if c<=1

T(n) = 1     , n = 1
T(n) = 1 + T ⌈n / 2⌉ ,   n > 1

T(n) = 1-c + c· lg(n - 1)

it is possible to prove it by complete induction

WEEK #5

i am still working on recursive proof.

Hi @ WEEK #4

hi everyone, Happy Thanksgiving!

i just read some of you guys' journal. it is awesome!

Ok, let's start talking about my feeling about Assignment 1.

For Assignment 1, Question 2.

I used some "weird" way which is Derivative to proof (n^3) + n < (3^n)

Do you remember we learn that in MAT137 ?

Great ! That is how i do it.

set f(n) = (n^3) + n - (3^n)

if we find some how the function is decreasing function in n ∈ [4 , +∞) , and f(4) < 0
that will makes (n^3) + n < (3^n)

i don't know if this is a good way to solve this problem in CSC236, but it works when i was learning MAT137.

Cheers, my friend.

=)