1. ## Induction Proofs

Problem 1: I need to use induction to prove that the number of binary strings of length n equals 2^n.

Problem 2. Number of binary strings of length at most n equals 2^(n+1) -1

Problem 3. for every integer n > 0 or n = 0 there are integers a and b such that 2a + 3b = n.

Can somebody help me out on these 3 problems, they are my last posts as i finish my course tomorrow! It be great help if you guys can show me these 3 questions cause they will be in exam i bet!

Thanks!

2. Originally Posted by kurac

Problem 3. for every integer n > 0 or n = 0 there are integers a and b such that 2a + 3b = n.
they're all easy. i'll do 3) and i'm sure you'll get help for 1) and 2) before your exam!

for n = 0 choose a = b = 0. assuming there are integers a, b such that 2a + 3b = n, we let c = a - 1 and d = b + 1. then 2c + 3d = 2a + 3b + 1 = n + 1, and our induction is complete.

3. For (1), if n= 1 the only binary strings of length 1 are "0" and "1" so there are $\displaystyle 2= 2^1$.

Assume that for some k, the number of binary strings of length k is $\displaystyle 2^k$. From each of those, you can create a new string of length k+1 by appending either a "0" or a "1"- so you can create 2 new strings of length k+1 from each string of length k.

For (2), The number of strings of length less than or equal to k+1 is the number of strings of length less than or equal to k plus the number of strings of length k+1.