0

Given:

$U(0)=4$

$U(n+1)=3+2\cdot U(n)$ ...recurrence case

$U(n)=7\cdot 2^n-3$

My Solution:

$U(n+1)=3+2\cdot U(n)$

$\frac{U(n+1)-3}{2}=U(n)$

$\frac{U(n+1)-3}{2}=7\cdot 2^n-3$

Since I know $U(0) =4$, and with that I can solve $U(1)=11$

$n = 0$

$\frac{U(0+1)-3}{2}=7\cdot2^0-3$

$4=4$ .... is this a proof?

Bernard
  • 175,478
NoobProgrammer
  • 5
  • 3
    If you already have U(n), what else do you want to solve? – pooja somani Jan 16 '19 at 10:58
  • "How to prove a recurrence" is a bit vague. When you have $$ U_{n+1} = 3 + 2U_{n} $$ this is quite clearly a recurrence. It's not clear what is required ... – Matti P. Jan 16 '19 at 11:01

1 Answers1

0

Not really a proof, but it contains the idea.

What you're doing should be formalized with induction.

Given: $U(0)=4$, $U(n+1)=3+2U(n)$

Conjecture: $U(n)=7\cdot 2^n-3$

Base of induction: $7\cdot2^0-3=4=U(0)$. Verified true.

Induction step: Assume $U(n)=7\cdot2^n-3$. Then $$ U(n+1)=3+2U(n)=3+2(7\cdot2^n-3)=2\cdot7\cdot2^{n}+3-6=7\cdot2^{n+1}-3. $$ End.

egreg
  • 238,574