Problem Solving: Recursively-defined Functions

*Note: This question is taken from problem set #3. I will present my solution to the assignment.

Q:

Consider the following recursively-de ned function:
\forall n \in N G(n) = 1, if n = 0
3G(n - 1) + 1, if n > 0

Gain some insight into G(n) through unwinding (also called repeated substitution). Make a conjecture about a closed-form for G(n), and then prove your conjecture.

1. UNDERSTANDING THE PROBLEM
First. Given the definition of G(n) for some natural number n, my tasks are
1) finding a closed-form for G(n) using unwinding
2) constructing a conjecture about (1)
3) proving (2)

2. DEVISING A PLAN
Second. Find the connection between G(n) and the closed-form of G(n). I am instructed to apply unwinding in the question. Thus, the closed-form of G(n) should be driven from the repeated substitution. Once I succeed in obtaining the closed-form of G(n), make a conjecture regarding G(n) and its closed form. I have seen similar questions before asking for a conjecture as well. In this type of question, a conjecture can be constructed by comparing the data and the unknown or by indicating the upper/lower bound of the unknown. In this case, it is very likely to a relation such as G(n) = closed-form of G(n).

3. CARRYING OUT THE PLAN
Third.
1) Unwinding G(n):

G(n) = 3G(n - 1) + 1

= 3[3G(n - 2) + 1] + 1 = 9G(n - 2) + 3 + 1

= 9[3G(n - 3) + 1] + 3 + 1 = 27G(n - 3) + 9 + 3 + 1

= 27[3G(n - 4) + 1] + 9 + 3 + 1 = 81G(n - 4) + 27 + 9 + 3 + 1

= [make a guess] 3^n + 3^(n - 1) + ... + 3^0

= (3^(n + 1) - 1) / 2

2) P(n): G(n) = (3^(n + 1) - 1) / 2

3) Claim: \forall n \in N, P(n)

Proof by simple induction

Base Case

When n = 0, G(0) = 1 [by the definition of G(n)] and (3^(0 + 1) - 1) / 2 = 1 as well.

Thus, P(0) is true.

Induction Step

Assume n \in N. Also assume that P(n) is true. So G(n) = (3^(n + 1) - 1) / 2. Then,

G(n + 1) = 3G(n + 1 - 1) + 1

= 3G(n) + 1

= 3[(3^(n + 1) - 1) / 2] + 1 # by IH

= [3(3^(n + 1)) - 3] / 2 + (2 / 2)

= (3^(n + 2) - 3 + 2) / 2

= (3^(n + 2) - 1) / 2

= (3^((n + 1) + 1) - 1) / 2

Therefore P(n) => P(n + 1). Conclude \forall n \in N, P(n).

4. LOOKING BACK

Fourth. Check the result.

G(1) = 3G(0) + 1 = 4 = (3^(2) - 1) / 2

G(2) = 3G(1) + 1 = 13 = (3^(3) - 1) / 2

G(3) = 3G(2) + 1 = 40 = (3^(4) - 1) / 2

G(4) = 3G(3) + 1 = 121 = (3^(5) - 1) / 2

G(5) = 3G(4) + 1 = 364 = (3^(6) - 1) / 2

Ice Age III

Dec. 1-08

The final term test is going to be held this Friday. Moreover, we have our CSC236 exam next week along with other exams for other CSC courses. I want to get over with this quickly.

I have learned to reason and justify various types of problems in this half year. I could see the strength of logic; however, it was really frustrating when I try to prove something very obvious yet not able to phrase it properly. If that happens, I would get paranoid and think: "Why do I think it is obvious?" Then I could hold my head for 30 minutes.

For my fellow students, good luck on you final exams.

Walking Towards the End

Nov. 28-08

It is almost the end of the term. Everybody is hunted by their assignments, tests and projects. My schedule has turned into a chaos as well. Anyway, I have handed in the assignment #3 this Monday. At first sight it looked easy, but it was actually pretty tough. On top of that, the assignment was extremely time consuming. I wonder how long it would cost me if I did that assignment alone.

FSA Continued

Nov. 19-08

I didn't go to the Monday lecture, therefore I had to catch up with the class. My friends told me that they were taught how to prove a DFSA. I reviewed Monday slides, but was confused at some details of the DFSA proof. Then, I traced the proof provided on the slides with paper and pen, but didn't work out. I think I need to clear my mind once, then come back to stare at the slides again. If it still doesn't solve my problem, then I will go and ask a TA.

Assignment #3 was released last week. I was determined to start the assignment earlier this time, so I did some brainstorm on it. It didn't look hard, but I could tell it would take me a while to complete it. Final problem set was posted as well on the bulletin board, and it is due this Friday. I have skimmed over the problem set and thought it could be considered as the warming up for assignment #3.

FSA

Nov. 14-08

We have proceeded to the topic of FSAs. I was delighted to know that we were going to work with diagrams and graphs. State invariant had to be clarified before constructing a DFSA. However once we have a working machine, we can easily confirm the correctness of the DFSA. That was what I really liked about this subject.

Problem set #5 was due today. Apparently, problem sets are more helpful than the textbook. Questions on the problem sets were well-designed and encouraged me to do more work.

Ice Age II

Nov. 5-08

The second term test is approaching. I haven't regained my confidence yet, and I cannot help myself being nerves about the test. Hopefully, I can stay calm on Friday.

Regular expressions was something completely new to me. I didn't even know there exists such a way to express languages. I didn't realize the significance of regular expressions until I was forced to face it in my CSC207 class. Now, I see the benefits of taking CSC236 and CSC207 together. The thing is that people cannot prove something that they are not aware of. Without a good understanding of the usage of regular expressions, I cannot possibly reason them properly. Thanks to the second assignment of CSC207 where I had some room to play with regular expressions, now I can concentrate more on its theoretical aspect. Again, I was very glad that I have managed to have both CSC207 and CSC236 in the same semester.

Happy Halloween

Oct. 29-08

Time passed very fast. I can hardly believe it is the end of October already.

Proving the program correctness is not terribly difficult to do, even through the proof can be tedious when justifying a program with tons of loops and if statements. When proving the accuracy of a program with double loops, I had a hard time to keep track of what exactly I was trying to prove at that moment. One of the TAs suggested me to list out the steps of the proof in the beginning and keep the solution for each phase in separate papers. I will definitely do what he said next time.

We handed in our assignments this Monday. The second assignment was harder than the first one, but it was a great enhancement on the lecture materials.

Checking Program Correctness

Oct. 24-08

The class has moved on to the new topic, Program Correctness. It was not as hard as the last topic so I was little relieved.

The due date for problem set #4 was extended to next Monday. The second assignment was posted this week. I haven't given any thoughts to the assignment yet. It is also due next Monday, so I have to rush through it during the weekend. It seems things have been really tight recently for every body. We just have to survive through this crisis.

Thanksgiving Is Over

Oct. 17-08

There was no lecture on Monday since it was Thanksgiving. I was stunned when the class discussed the master theorem because I didn't have any clue of what we were talking about. To keep up with the lecture, I read about the master theorem in the textbook but was not really convinced how it works. I thought it would be helpful if I could see more examples applying the theorem. For this purpose, I went to library but didn't find any book useful. I will go to the help centre next week.

Problem set #3 was due today and we also got our tests back. I did very poor on the first term test and I am losing my confidence. At least I can try to work harder next time.

Ice Age I

Oct. 6-08

This is the time, where I would go around and ask people: "What would you do if this is your last day on the earth?" Whenever you hear me talking about things such as "the end of world" or "the coming of the ice age," then there is probably a term test approaching. I am starting to get tense. Just to relax myself, I will watch a horror movie tonight and begin my test study tomorrow.

Today, we have examined some questions on Fibonacci sequence and binary trees. I have come across the Fibonacci sequence several times in my life, but I never liked it. To make things worse, I didn't get the proof of F(n) = (phi^n - phi_hat^n)/sqrt(5). After the lecture, I stared at the slide trying to find out why phi = (1 + sqrt(5))/2. Two hours later, I finally noticed that I could just go ahead to solve r^2 = r + 1 to obtain the root (this was written on the next page of the slides.) Obviously, I was losing my focus and needed to pull my mind away from CSC236 for a while.

The End of the Starter

Oct. 3-08

Last week of September we moved to chapter 3, Recursive Definitions. The focus of the course has shifted away from induction, but it doesn't change the fact that we are still dealing with inductive proofs. I guess we can never get away from induction in this course.

The concept of recursion is by no mean a new topic to most of the students including me. I believe most people in the class already had plenty of experiences with recursive program before. However when I looked into the logic behind recursion, I could see a whole new aspect of the topic. One thing that I really liked about this topic is "unwinding." I have never heard a problem-solving method with such a fascinating name. "Unwinding" is a very complicated process to look for the pattern of a function. I didn't understand it at all when Danny explained it in the lecture. I revisited lecture slides afterwards and tried to recall what Danny said. Eventually, I got it after staring at the slides for one and half hours.

Endless Realm of Induction

Sept. 26-08

This was our third week on the topic of induction. It is amazing how well inductive reasoning coexists with other mathematical principals such as Principle of Well-Ordering. We have spent all the past weeks studying induction, now I don't have any hesitation using complete induction anymore. It was not as if I went through every practice question in the textbook to get myself familiar with strong induction. It was rather due to the effective lecture style which was newly adopted this year. Thanks to the tablet, I was able to fully concentrate on the lecture instead of putting all my efforts copying the notes [since I was such a slow writer.]

I promised myself to work on the assignment during last weekend, but I couldn't. Whatever I do, it has to be done till next Monday. I have done some scratch works for the assignment, now I need to phrase them into solid proofs. Problem set #2 was due today. Because my mind was taken over by the concerns regarding the first assignment, I completely forgot about the problem set. It was not until the last night when I suddenly remembered to finish it. I need to check the course website more frequently to remind myself what is coming up next.

Tasting Various Induction Flavours

Sept. 19-08

Complete induction was introduced in the first lecture of week two. We have gone through practice questions of complete induction. It is a very convenient technique to prove complicated statements. Depending on the question, complete induction may require more writings than simple induction does, but a strongly inductive proof can be used to solve a wide variety of problems. Somehow, I felt uncomfortable using complete induction simply because assuming the truth of all the previous cases just sounds a little too good. I think this sense of oddness will naturally disappear once I have enough experience with the applications of complete induction.

The first problem set was due today, and it was a good review of lecture materials. In the other hand, assignment #1 which was posted this week appeared very challenging. I better start working on it right away.

First Week of CSC236H1 Fall 2008

Sept. 12-08

CSC236, a theory course of computer science, started this week with three lectures in a row. All lectures focused on the Principle of Simple Induction this week. I have learned the basics of both simple and complete induction in CSC165, so I had a good idea of the material we were doing. Otherwise, it would be very problematic if I cannot even keep up with week-one material although I did have difficulties understanding chapter zero of the textbook.

Chapter zero was supposed to be a review for those who had certain degrees of background for CSC236. When I skimmed through this chapter, I was stunned at some unfamiliar words such as "proper subset", "partial order," and "contiguous sub sequence." I had to reread the chapter several times to have a good grip of its content.

Regarding the lecture style, I am glad that Danny discarded the idea of using blackboards this year. I absolutely love his new medium, the tablet. Writings tend to be more packed in a blackboard since it does not save what was written ten minutes ago. It is easier to read off from a tablet.