Let $P(n) = 2P(n-1) + n, P(1) = 3.$ Use induction to show that $$P(n) = 3(2^n) - n - 2$$
Highly verbose solutions are greatly appreciated.
$\begingroup$
$\endgroup$
5
-
2$\begingroup$ Where are you stuck? $\endgroup$lab bhattacharjee– lab bhattacharjee2014-03-09 04:59:03 +00:00Commented Mar 9, 2014 at 4:59
-
$\begingroup$ Usually, my professor solves these by doing something along these lines: take the non recursive portion, suppose it is true for p(n-1), then plug that into the recursive portion to replace n-1, and then simplify. How this works, as an inductive argument is beyond me. Perhaps a little clarification for this method, and if you're familiar with it, a solution with explanation of thought process? Thanks a million in advance. $\endgroup$jvb93– jvb932014-03-09 05:16:30 +00:00Commented Mar 9, 2014 at 5:16
-
$\begingroup$ Actually, I solved it, but I do not have sufficient reputation to post my answer yet. You'll hear back from me in a few hours... $\endgroup$jvb93– jvb932014-03-09 06:08:41 +00:00Commented Mar 9, 2014 at 6:08
-
$\begingroup$ If you want a proof by induction, I am not sure where you are having trouble. The inductive step is simply: $$P(n+1) = 2P(n)+(n+1) = 2\left(3(2^n)-n-2\right) + (n+1) = 3(2^{n+1})-n-3$$ $\endgroup$Macavity– Macavity2014-03-09 06:12:04 +00:00Commented Mar 9, 2014 at 6:12
-
$\begingroup$ Yes this is correct. Thank you. $\endgroup$jvb93– jvb932014-03-09 17:53:00 +00:00Commented Mar 9, 2014 at 17:53
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
The formation of the question suggests that a general solution is of the type: $$P(n) = k\cdot2^n + an + b$$ with integers $a, b , k$. So $P(1) = 3 \implies 3 = 2k + a + b$ (1). Let $n = 2$ in the equation, $P(2) = 2\cdot3 + 2 = 8 = 4k + 2a + b$ (2), and let $n = 3$ gives: $P(3) = 2\cdot8 + 3 = 19 = 8k + 3a + b$ (3).
Solving the system (1), (2), and (3) gives: $b = -2, a = -1, k = 3$. So $P(n) = 3\cdot2^n - n - 2$.
-
$\begingroup$ Any methods that avoid using systems of equations? $\endgroup$jvb93– jvb932014-03-09 05:17:03 +00:00Commented Mar 9, 2014 at 5:17
-
$\begingroup$ You can use generating function. $\endgroup$DeepSea– DeepSea2014-03-09 05:25:48 +00:00Commented Mar 9, 2014 at 5:25
-
$\begingroup$ Can you give an example? $\endgroup$jvb93– jvb932014-03-09 05:30:45 +00:00Commented Mar 9, 2014 at 5:30
-
$\begingroup$ @jvb93: ok. let a(0) = 1, and a(n) = 3*a(n-1) + 1. Find a formula for a(n). You let A(x) = a(0) + a(1)x + a(2)x^2 +...+ a(n)x^n +....then you plug 3*a(n-1) + 1 in place of a(n), and split it in two sums and in term of A(x). Solve A(x) and expand A(x) as a power series, then the n-th term of the power series is the n-th term of your sequence. Try it. $\endgroup$DeepSea– DeepSea2014-03-09 06:12:29 +00:00Commented Mar 9, 2014 at 6:12
-
$\begingroup$ This is pretty cool, though isn't exactly what my professor is looking for, unfortunately. I do appreciate your response. $\endgroup$jvb93– jvb932014-03-09 17:54:01 +00:00Commented Mar 9, 2014 at 17:54
$\begingroup$
$\endgroup$
Here's what I found after consulting some other people with this issue, and some additional study materials:
Let $p(n) = 3(2^n)-n-2$ for $n>=1$, then $p(1) = 3$, so $p(1)$ is true.
Suppose $k>1$ is an integer and $p(k-1)$ is true. So $p(k-1) = 3(2^{k-1})-(k-1)-2$
By the given relation:
$p(k) = 2(3(2^{k-1})-(k-1)-2)+k$
Simplify:
$p(k) = 3(2^k)-k-2$
So it is true that $p(n) = 3(2^n)-n-2$ for $n>=1$