1

Suppose we have a sequence of numbers defined recursively as follows: $$ d_n = \begin{cases} 0 & \text{if } n=1; \\ 2d_{n-1}+2 & \text{if } n \geqslant 2. \end{cases} $$ Using mathematical induction, prove that for every integer $n\geqslant 1, d_n = 2^n -2$.

I have a few questions about this assignment.

  1. We need to use mathematical induction, but do we still need a basis like $n=1$, because it already says that $d_n = 0$

  2. Since $d_n =0$ for $n=1$ and $d_{n-1} +2$ for $n \ge 2$. And the fact that $d_n = 2^n -2$, and for the induction part $n$ needs to be $k$, do we then do this: $$ 2^k -2 = 2(2^k-1 +2) $$ or do we do $$ 2^k -2 = 2(2^k +2) $$

  3. Same question for $n = k+1$: $$ 2^k+1 -2 = 2(2^k +2) $$ or do we do $$ 2^k+1 -2 = 2(2^k+1 +2) $$

Thanks in advance. Sorry if i wasnt to clear in my title.

bassie
  • 19

2 Answers2

0

I don't really understand your reasoning. You know that $d_1=0$, with checks out with $d_1=2^1-2$. Now assume that the relation holds up to $n$, this is your induction hypothesis. Then $$ d_{n+1}=2d_n+2$$ And you just have to use your induction hypothesis. I'll let you go on from here.

user438666
  • 2,040
  • 1
  • 9
  • 23
0

For induction, you are proving that a certain statement holds for every number greater than or equal to your base case. You can say for example that $d_6 = 13$ and that $d_{n+1}$ is some function of $d_n$ and this will define a function for integers greater than or equal to $6$. So in your case, your function $d$ is defined for integers greater than or equal to $1$.

For the induction step, just assume that $d_n = 2^n + 2$ and by assumption you have $d_{n+1} = 2d_n + 1 $. You can complete the problem by showing that these facts together imply that $d_{n+1} = 2^{n+1} + 2$. This is essentially all there is to a proof by induction.

Bernard W
  • 2,141
  • I know what induction is, but this question was a little bit unclear for me. – bassie Oct 14 '17 at 23:51
  • just sub in $d_n = 2^n+2$ into $d_{n+1} = 2d_n + 1$ and rearrange to show that $d_{n+1} = 2^{n+1} + 2$. That's pretty much the only way to do this question. It is unclear what you are doing in points 2 and 3 – Bernard W Oct 15 '17 at 00:08
  • because we need to use n =k and n = k+1 at school. I was wondering i i needed to use k-1 or k at the second part of 2. Same holds for 3, k or k+1 – bassie Oct 15 '17 at 00:36
  • For the induction step, you assume the formula holds for some arbitrary value (whatever letter you use to denote this value doesn't matter, but it must be arbitrary) and then show the formula holds for the next value. – Bernard W Oct 15 '17 at 06:37