# Tagged Questions

53 views

### How to prove a very basic algorithm by induction

I just studied proofs by induction on a math book here and everything is neat and funny: the general strategy is to assume the LHS to be true, and use it to prove the RHS (for the inductive step). Now ...
127 views

### Proving by induction that a palindrome contains an even number of $b$s and $c$s

Suppose we want to construct palindromes that contain an $aa$ in the middle if the length is even and an $a$ in the middle if the length is odd. I'm trying to prove by induction that all of these ...
86 views

### Inductive Definition of regular expression

Give an inductive definition of regular expressions that do not use the star operator. Prove by induction on this definition that every such expression denotes a finite language not containing lambda. ...
88 views

### How to prove that a series is equal to a recursive algorithm

I have the following sequence: $$y_n = \int_0^1 \frac{x^n}{x+5}\,dx, n = 0,1,\dots$$ Now I have the following recursive algorithm: $$y_0 = \log{6} - \log{5}$$  y_n = \frac{1}{n} - 5y_{n-1}, n ...
128 views

### Termination of a Fast Exponentiation problem

Here's the problem I am stuck on. There exists a fast exponentiation program like the following: Given inputs a in the set of all Real numbers, b in the set of Natural numbers, initialize ...